1D Dynamic Programming

The best way to get fluent at dynamic programming is to internalize a handful of 1D DP patterns - problems where the state is a single index and each answer depends on a few earlier ones. Climbing stairs, house robber, and coin change cover most of the shapes you'll meet.

Define the state, then the transition

Every DP is two decisions: what does dp[i] mean? (the state) and how does dp[i] depend on earlier entries? (the transition). Nail those two and the code writes itself.

House robber - maximize the loot from houses in a row, but you can't rob two adjacent houses:

// dp[i] = max loot from houses 0..i
int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;                 // dp[i-2], dp[i-1]
    for (int money : nums) {
        int take = prev2 + money;             // rob this house (skip the previous)
        int skip = prev1;                     // don't rob it
        int curr = Math.max(take, skip);      // transition: best of the two choices
        prev2 = prev1; prev1 = curr;
    }
    return prev1;
}

The state is "best loot up to house i"; the transition is "either rob house i (adding it to the best from two houses back) or skip it (keeping the best from the previous house), take the max." Only the last two values matter, so it runs in O(1) space.

When the transition ranges over choices: coin change

Some transitions consider several options and take the best. Coin change - fewest coins to make an amount - defines dp[a] as the minimum coins for amount a, trying every coin as the last one:

// dp[a] = fewest coins to make amount a
int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);              // "infinity" sentinel
    dp[0] = 0;                                // base case: 0 coins for amount 0
    for (int a = 1; a <= amount; a++)
        for (int coin : coins)
            if (coin <= a)
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);   // use this coin last
    return dp[amount] > amount ? -1 : dp[amount];
}

Here the transition loops over coins: dp[a] is one more than the best way to make a - coin, minimized over all coins. It's O(amount × coins).

The recipe

For any 1D DP: (1) define dp[i] in words; (2) write the transition - how dp[i] builds from smaller indices; (3) set the base case(s); (4) decide the iteration order so dependencies are ready; (5) optionally reduce space if only the last few entries are needed.