We use dynamic programming approach when

General
1

we use dynamic programming approach when

2

LectureNotes said we use dynamic programming approach when

Dynamic programming (DP) is a powerful technique used in computer science and mathematics to solve problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. Here are the key scenarios when we use the dynamic programming approach:

1. Overlapping Subproblems
Dynamic programming is particularly useful when a problem can be broken down into smaller subproblems that are reused multiple times. If the same subproblems are solved repeatedly, DP can save these solutions to avoid redundant calculations. For example, in the Fibonacci sequence, calculating F(n) involves calculating F(n-1) and F(n-2), which in turn requires the same subproblems multiple times.

2. Optimal Substructure
A problem exhibits optimal substructure if an optimal solution to the problem can be composed of optimal solutions to its subproblems. This property is essential for applying dynamic programming. For instance, in the shortest path problem, the shortest path from a starting node to a destination node can be determined by combining the shortest paths from the starting node to intermediate nodes and from those nodes to the destination.

3. Efficiency
Dynamic programming is used when a problem’s brute-force solution is inefficient due to exponential time complexity. By storing the results of subproblems (memoization) or building solutions iteratively (tabulation), DP reduces the time complexity significantly. For example, the naive recursive solution for the Fibonacci sequence has exponential time complexity O(2^n), while the DP approach reduces it to linear time O(n).

4. Decision-Making Problems
DP is often used in problems that involve making a sequence of decisions to achieve the best outcome. Examples include the Knapsack problem, where the goal is to maximize the total value of items that can be carried in a knapsack of limited capacity, and the Coin Change problem, where the objective is to find the minimum number of coins needed to make a specific amount.

5. Problems with a Recursive Nature
Problems that can be naturally expressed in a recursive form are good candidates for dynamic programming. If a problem can be defined in terms of smaller instances of itself, DP can be applied to solve it efficiently. For example, the Longest Common Subsequence (LCS) problem can be solved using a recursive approach that compares characters of two sequences and builds the solution from subproblems.

Examples of Dynamic Programming Applications:

  • Fibonacci Sequence: Calculating the n-th Fibonacci number.
  • Knapsack Problem: Maximizing the value of items in a knapsack with a weight limit.
  • Longest Common Subsequence (LCS): Finding the longest subsequence common to two sequences.
  • Matrix Chain Multiplication: Determining the optimal way to multiply a chain of matrices.
  • Edit Distance: Finding the minimum number of operations required to convert one string into another.

Conclusion

Dynamic programming is a versatile technique used to solve complex problems efficiently by leveraging the properties of overlapping subproblems and optimal substructure. It is particularly useful in scenarios where brute-force methods are impractical due to their high computational cost. By storing and reusing the results of subproblems, DP significantly reduces the time complexity and makes it feasible to solve large-scale problems.