Day41--动态规划--121. 买卖股票的最佳时机，122. 买卖股票的最佳时机 II，123. 买卖股票的最佳时机 III

Day41–动态规划–121. 买卖股票的最佳时机，122. 买卖股票的最佳时机 II，123. 买卖股票的最佳时机 III

121. 买卖股票的最佳时机

方法：暴力

思路：

两层遍历

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (prices[j] > prices[i]) {
                    res = Math.max(res, prices[j] - prices[i]);
                }
            }
        }
        return res == Integer.MIN_VALUE ? 0 : res;
    }
}

方法：贪心

思路：

记录取“最左”“最小”价格

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int minPrice = Integer.MAX_VALUE;
        int res = 0;
        for (int i = 0; i < n; i++) {
            // 取“最左”“最小”价格
            minPrice = Math.min(minPrice, prices[i]);
            // 更新最大利润
            res = Math.max(res, prices[i] - minPrice);
        }
        return res;
    }
}

方法：动态规划

思路：

1. dpi指的是在第i天，能获取的最大利润（手里的钱）
2. 递推公式：
   1. 要么就是继续持有，要么买今天的（覆盖原来的）dp[0] = Math.max(dp[0], -prices[i]);
   2. 要么保持前些天卖出的钱，要么今天卖出dp[1] = Math.max(dp[1], dp[0] + prices[i]);
   3. 初始化：dp[0] = -prices[0]; dp[1] = 0;
   4. 遍历顺序：正序

// 动态规划
class Solution {
    public int maxProfit(int[] prices) {
        // dpi指的是在第i天，能获取的最大利润（手里的钱）
        // 每天交易，交易有买入卖出两种状态
        // dp[0]代表买入，dp[1]代表卖出
        int[] dp = new int[2];

        // 初始化
        dp[0] = -prices[0];
        dp[1] = 0;

        for (int i = 1; i < prices.length; i++) {

            // 解释一：要么就是继续持有，要么买今天的（覆盖原来的）
            // 解释二：这里就是取minPrice了，有没有看出来
            dp[0] = Math.max(dp[0], -prices[i]);

            // 解释一：要么保持前些天卖出的钱，要么今天卖出
            // 解释二：每天算一下，是今天卖出能赚取更多，还是按前些天卖的能赚更多
            dp[1] = Math.max(dp[1], dp[0] + prices[i]);
        }
        // 最后一天，肯定要卖出才有最大收益，所以返回dp[1]
        return dp[1];
    }
}

方法：动态规划

思路：

二维数组版本，第一次写的时候可以写这个，遍历出来，看到每一层的变化。

// 动态规划
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[n][2];
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
        }
        return dp[n - 1][1];
    }
}

122. 买卖股票的最佳时机 II

思路：

123. 买卖股票的最佳时机 III

思路：