Core Concept of Dynamic Programming

Dynamic Programming (DP) is an algorithmic technique used when a problem exhibits overlapping subproblems and optimal substructure. Unlike greedy algorithms—which make locally optimal choices without considering previous states—DP builds solutions incrementally, where each state is derived from one or more prior states.

For instance, in the 0/1 knapsack problem, the value dp[j] represents the maximum value achievable with a weight capacity j. Its computed as:

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

This recurrence depends explicitly on previously computed states. In contrast, a greedy approach might simply pick items by highest value-to-weight ratio without regard to prior selections, which often fails to yield the global optimum.

The key distinction: DP relies on state transitions from earlier solutions; greedy makes immediate, isolated choices.

Systematic Approach to Solving DP Problems

Rather than memorizing recurrence relations, a structured five-step method ensures deeper understanding:

1. Define the DP array and its indices: Clearly state what dp[i] represents.
2. Derive the recurrence relation: Express how current states depend on previous ones.
3. Initialize the DP array: Set base cases correctly based on problem constraints.
4. Determine iteration order: Decide whether to iterate forward, backward, or in another pattern.
5. Validate with manual simulation: Compute small examples by hand to verify logic.

Skipping initialization or misdefining state meaning often leads to subtle bugs.

Debugging Strategy for DP Solutions

When a DP solution fails:

• Print the entire dp array after computation.
• Compare it against a manually derived version for a small input.
• If they match, the issue likely lies in the recurrence, initialization, or traversal order.
• If they differ, inspect the code implementation for off-by-one errors or incorrect indexing.

This disciplined approach replaces guesswork with targeted analysis.

Example 1: Fibonacci Number (LeetCode 509)

Problem: Compute the n-th Fibonacci number, where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.

DP Analysis:

1. dp[i] = Fibonacci number at index i.
2. Recurrence: dp[i] = dp[i-1] + dp[i-2].
3. Initialization: dp[0] = 0, dp[1] = 1.
4. Iterate from i = 2 to n.
5. For n = 5, expected sequence: [0, 1, 1, 2, 3, 5].

Implementation:

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];
}

Time: O(n), Space: O(n).

Example 2: Climbing Stairs (LeetCode 70)

Problem: Count distinct ways to reach the top of n stairs, taking 1 or 2 steps at a time.

DP Analysis:

1. dp[i] = number of ways to reach step i.
2. To reach step i, you can come from i-1 (1 step) or i-2 (2 steps): dp[i] = dp[i-1] + dp[i-2].
3. Base cases: dp[0] = 1 (one way to stay at ground), dp[1] = 1.
4. Iterate forward from 2 to n.
5. Sequence matches Fibonacci starting from index 1.

Implementation:

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

Time: O(n), Space: O(n).

Example 3: Min Cost Climbing Stairs (LeetCode 746)

Problem: Given cost[i] to step on stair i, find the minimum cost to reach the top (beyond last stair), starting from step 0 or 1.

DP Analysis:

1. dp[i] = minimum cost to reach stair i.
2. To reach i, you could have come from i-1 (paying cost[i-1]) or i-2 (paying cost[i-2]):

   dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
   

3. Initialization: dp[0] = 0, dp[1] = 0 (starting points incur no cost).
4. Iterate from i = 2 to n (where n = cost.size()).
5. Final answer: dp[n] (top is one step beyond last index).

Implementation:

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }
    return dp[n];
}

Time: O(n), Space: O(n).