Solving dynamic programming problems systematically typically involves five key steps:

1. Define the dp array (table) and the meaning of its indices.
2. Determine the recurernce relation.
3. Initialize the dp array correctly with base cases.
4. Select the correct iteration order.
5. Trace example values to verify logic.

Fibonacci Numbers

The Fibonacci sequence is a classic example where each number depends on the previous two ($F(n) = F(n-1) + F(n-2)$). A space-optmiized iterative approach avoids storing the full history, using only variables to track the state.

class Solution {
    public int fib(int n) {
        if (n <= 1) return n;
        
        int first = 0;
        int second = 1;
        int current = 0;
        
        for (int i = 2; i <= n; i++) {
            current = first + second;
            first = second;
            second = current;
        }
        return second;
    }
}

Climbing Stairs

This problem maps directly to the Fibonacci sequence but shifts the base conditions. To reach step $n$, one must have come from either step $n-1$ or step $n-2$. The transition remains additive, though initial values differ: reaching step 1 requires 1 way, while step 2 requires 2 ways.

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int prevTwo = 1;
        int prevOne = 2;
        int result = 0;
        
        for (int i = 3; i <= n; i++) {
            result = prevTwo + prevOne;
            prevTwo = prevOne;
            prevOne = result;
        }
        return prevOne;
    }
}

For generalized scenarios where multiple step size are allowed (up to $m$), the inner loop expands to check all valid previous states.

class Solution {
    public int climbStairsGeneralized(int n, int m) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m && j <= i; j++) {
                dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
}

Min Cost Climbing Stairs

In this variation, every step incurs a specific cost to leave it. The goal is to minimize the total expense to reach the top floor (beyond the last array index). At any point $i$, the minimum cost is the lower sum of coming from the immediate predecessor plus their step cost, or the predecessor's predecessor plus their cost.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int prev2 = 0;
        int prev1 = 0;
        
        for (int i = 2; i <= n; i++) {
            int current = Math.min(prev1 + cost[i - 1], prev2 + cost[i - 2]);
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}

When debugging initialization issues in such problems, manually tracing small input arrays often reveals discrepancies in base case assumptions, particularly regarding whether starting indices incur costs.