Complete Guide to Dynamic Programming

Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends on the optimal solutions to its subproblems.

Key Concepts

1. Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times.
2. Optimal Substructure: The optimal solution to the problem contains optimal solutions to the subproblems.

DP Approaches

• Memoization (Top-Down): Solve the bigger problem by recursively solving smaller subproblems and caching the results.
• Tabulation (Bottom-Up): Solve the subproblems first and use their results to build up the solution to the bigger problem.

Fibonacci Example (Bottom-Up in C++)

int fib(int n) {
    if (n <= 1) return n;
    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}