Linear DP: Climbing Stairs, House Robber, and Stock Trading

Climbing Stairs Family

Classic Climbing Stairs (LeetCode 70)

The rule is: dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[1] = 1, dp[2] = 2.

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int temp = prev1 + prev2;
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
}

Jump Game I (Greedy Variant)

Can you reach the last index? Track the maxReach.

boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false; // Current index is unreachable
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

House Robber Family

House Robber I (Linear)

You cannot rob adjacent houses. $dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$

int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int prev2 = nums[0], prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < nums.length; i++) {
        int current = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

House Robber II (Circular)

Houses are organized in a circle. You cannot rob both the first and the last.

int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    // Compare two scenarios: skip last house OR skip first house
    return Math.max(robRange(nums, 0, nums.length - 2), 
                    robRange(nums, 1, nums.length - 1));
}

private int robRange(int[] nums, int start, int end) {
    int prev2 = 0, prev1 = 0;
    for (int i = start; i <= end; i++) {
        int temp = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = temp;
    }
    return prev1;
}

Stock Trading Family

Best Time to Buy and Sell Stock (Single Transaction)

int maxProfit(int[] prices) {
    int minPrice = Integer.MAX_VALUE, globalMaxProfit = 0;
    for (int p : prices) {
        minPrice = Math.min(minPrice, p);
        globalMaxProfit = Math.max(globalMaxProfit, p - minPrice);
    }
    return globalMaxProfit;
}

Stock II (Multiple Transactions)

Greedy: If the price rises tomorrow, buy today.

int maxProfit(int[] prices) {
    int totalProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i-1]) totalProfit += prices[i] - prices[i-1];
    }
    return totalProfit;
}

Stock with Cooldown (1-day rest after sell)

State-Machine DP:

• hold: Max profit currently holding a stock.
• sold: Max profit having just sold a stock (currently in cooldown).
• rest: Max profit available for buying (cooldown finished).

int maxProfit(int[] prices) {
    int hold = Integer.MIN_VALUE, sold = 0, rest = 0;
    for (int p : prices) {
        int prevSold = sold;
        sold = hold + p;
        hold = Math.max(hold, rest - p);
        rest = Math.max(rest, prevSold);
    }
    return Math.max(sold, rest);
}

Summary Summary