动态规划：买卖股票的最佳时机 I、II、III 详解

1 题目列表

买卖股票的最佳时机 121. 买卖股票的最佳时机 - 力扣（LeetCode）

买卖股票的最佳时机 II 122. 买卖股票的最佳时机 II - 力扣（LeetCode）

买卖股票的最佳时机 III 123. 买卖股票的最佳时机 III - 力扣（LeetCode）

2 DP 五部曲

• dp 数组及其下标的含义
• 状态转移方程
• 初始化
• 遍历顺序
• 手动模拟

3 买卖股票的最佳时机

3.1 思路

贪心思路：

class Solution {
    public int maxProfit(int[] prices) {
        int low = Integer.MAX_VALUE;
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            low = Math.min(low, prices[i]);
            profit = Math.max(profit, prices[i] - low);
        }
        return profit;
    }
}

动态规划思路：

第一步：定义 dp[i][0] 和 dp[i][1] 两个状态。

• dp[i][0]：表示第 i 天持有股票时，能获得的最大现金（利润）。
• dp[i][1]：表示第 i 天不持有股票时，能获得的最大现金（利润）。 这里的'现金'可以理解为：初始现金为 0，买入股票会减少现金（所以是负数），卖出股票会增加现金。

第二步：状态转移。

• 持有股票的状态（dp[i][0]）：dp[i][0] = Math.max(dp[i-1][0], -prices[i]) 两种情况取最大值：

  1. 第 i-1 天就持有股票，第 i 天继续持有（状态不变）：dp[i-1][0]；