Common Dynamic Programming Problems

Common Dynamic Programming Problems

Dynamic Programming (DP) appears in many real-world and competitive programming problems. Here are some classic examples and how DP helps solve them efficiently.

1. Fibonacci Series

Problem: Find the n-th Fibonacci number.

DP Relation: F(n) = F(n-1) + F(n-2)

Time Complexity: O(n)

2. 0/1 Knapsack Problem

Problem: Given weights and values of items, find the maximum value that can be carried in a knapsack of capacity W.

DP Relation:

dp[i][w] = max(
    value[i-1] + dp[i-1][w - weight[i-1]],
    dp[i-1][w]
)

Time Complexity: O(N × W)

3. Longest Common Subsequence (LCS)

Problem: Find the length of the longest subsequence common to two strings.

DP Relation:

if X[i-1] == Y[j-1]:
    dp[i][j] = 1 + dp[i-1][j-1]
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Time Complexity: O(m × n)

4. Matrix Chain Multiplication

Problem: Find the most efficient way to multiply matrices.

DP Relation:

dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost)

5. Coin Change Problem

Problem: Count ways to make change for a given amount using available coins.

dp[i] = dp[i] + dp[i - coin]

Time Complexity: O(N × amount)

6. Longest Increasing Subsequence (LIS)

Problem: Find the length of the longest subsequence that is strictly increasing.

dp[i] = 1 + max(dp[j]) where arr[j] < arr[i]

Time Complexity: O(n²)

7. Edit Distance (Levenshtein Distance)

Problem: Find minimum edits (insert, delete, replace) to convert one string into another.

if X[i] == Y[j]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Time Complexity: O(m × n)

8. Subset Sum / Partition Problem

Problem: Check if a subset with a given sum exists.

dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]

9. Rod Cutting Problem

Problem: Maximize profit by cutting a rod into pieces.

dp[i] = max(price[j] + dp[i-j-1])

10. Shortest Path (Floyd–Warshall Algorithm)

DP Relation:

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

Conclusion

Dynamic Programming problems often follow common patterns. By recognizing subproblem structures and writing recurrence relations, complex problems can be solved efficiently. Mastering these problems builds strong algorithmic intuition essential for competitive programming and technical interviews.