线性 DP：爬楼梯、打家劫舍、买卖股票

爬楼梯系列

经典爬楼梯

dp[i] = dp[i-1] + dp[i-2]，base case：dp[1]=1, dp[2]=2。

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) { int c = a + b; a = b; b = c; }
    return b;
}

跳跃游戏 I（贪心变体）

每个位置能否到达终点？维护当前能到达的最远距离 maxReach：

boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;  // 当前位置不可达
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

打家劫舍系列

打家劫舍 I（线性）

不能偷相邻的两间房，求最大金额。

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

int rob(int[] nums) {
    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 curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

打家劫舍 II（环形）

房子首尾相连，偷了第一间就不能偷最后一间：

int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    // 分两种情况：偷 [0..n-2] 或 偷 [1..n-1]，取最大
    return Math.max(robRange(nums, 0, nums.length - 2),
                    robRange(nums, 1, nums.length - 1));
}

int robRange(int[] nums, int left, int right) {
    int prev2 = 0, prev1 = 0;
    for (int i = left; i <= right; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

买卖股票系列

买卖一次（最大利润）

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

买卖多次（无限次）

任何时候可买卖，贪心：只要明天涨，今天就买：

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

含冷冻期（买卖后需冷冻一天）

状态机 DP：用三个状态描述每天的情况：

• hold：持有股票的最大利润
• sold：刚卖出（进入冷冻期）的最大利润
• rest：冷冻期结束后休息的最大利润

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 状态买）
        rest = Math.max(rest, prevSold); // 今天休息（从 sold 或 rest 转换）
    }
    return Math.max(sold, rest);
}

最多 k 次交易

dp[i][j][0/1]：第 i 天，已完成 j 次交易，0=未持有/1=持有。

int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (n == 0 || k == 0) return 0;
    if (k >= n / 2) {  // 相当于无限次
        int profit = 0;
        for (int i = 1; i < n; i++)
            if (prices[i] > prices[i-1]) profit += prices[i] - prices[i-1];
        return profit;
    }
    // dp[j][0] = 完成 j 次买卖后不持股的最大利润
    // dp[j][1] = 完成 j-1 次买卖、当前持股的最大利润
    int[][] dp = new int[k + 1][2];
    for (int j = 0; j <= k; j++) dp[j][1] = Integer.MIN_VALUE;
    for (int p : prices) {
        for (int j = k; j >= 1; j--) {
            dp[j][0] = Math.max(dp[j][0], dp[j][1] + p);      // 卖出
            dp[j][1] = Math.max(dp[j][1], dp[j-1][0] - p);    // 买入（开始第 j 次）
        }
    }
    return dp[k][0];
}

小结：线性 DP 的常见模式