刷题日记 24.5.10

lc123. 买卖股票的最佳时机 III（HD）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

完成交易的次数是有限的，且次数相对较少，所以比股票IV简单

能确定的五种状态分别是：

还没有买过股票
第一次买了股票，但是没有卖出
第一次卖出股票
第一次卖出股票后，再次买入股票
第二次卖出股票

显然，第一个状态的利润为 0，因此我们不记录。我们将后面四个状态分别记录为 $buy_1,sell_1,buy_2,sell_2$

针对 $buy_1$ ，对于第 $i$ 天，我们可以不买入股票，也可以以 $price[i]$ 的价格买入股票。此时 $buy_1$ 的状态转移方程为 $buy_1 = max(buy_1', -prices[i])$

这里的 $buy_1'$ 表示第 $i - 1$ 天的状态，主要和第 $i$ 天做区分，下文同理

针对 $sell_1$ , 对于第 $i$ 天，我们可以卖出手里的股票，也可以不卖出。此时 $sell_1$ 的状态转移方程为 $sell_1 = max(sell_1', buy_1' + prices[i])$

同理可得， $buy_2$ 和 $sell_2$ 的状态转移方程应该为

$buy_2 = max(buy_2', sell_1' - prices[i])$

$sell_2 = max(sell_2', buy_2' + prices[i])$

在考虑边界条件时，应当注意到：无论题目中是否允许 “在同一天买入并且在同一天卖出” 这一操作，最终答案都不会受到影响，因为这一操作带来的收益为0

因此总的状态转移方程是

$\begin{cases} buy_1 = max(buy_1, -prices[i]) \\ sell_1 = max(sell_1, buy_1 + prices[i]) \\ buy_2 = max(buy_2, sell_1 - prices[i]) \\ sell_2 = max(sell_2, buy_2 + prices[i]) \end{cases}$

例如在计算 $sell_1$ 时，我们直接使用 ${buy}_1$ 而不是 $buy_1'$ 进行转移。 ${buy}_1$ 比 ${buy}_1'$ 多考虑的是在第 $i$ 天买入股票的情况，而转移到 ${sell}_1$ 时，考虑的是在第 $i$ 天卖出股票的情况，这样在同一天买入并且卖出收益为零，不会对答案产生影响。同理对于 ${buy}_2$ 以及 ${sell}_2$ ，我们同样可以直接根据第 $i$ 天计算出的值来进行状态转移。

那么对于边界条件，我们考虑第 $i=0$ 天时的四个状态： ${buy}_1$ 即为以 ${prices}[0]$ 的价格买入股票，因此 $buy1=−prices[0]$ ； ${sell}_1$ 即为在同一天买入并且卖出，因此 ${sell}_1=0$ ； ${buy}_2$ 即为在同一天买入并且卖出后再以 $prices[0]$ 的价格买入股票，因此 $buy2=−prices[0]$ ；同理可得 $sell_2=0$ 。我们将这四个状态作为边界条件，从 $i=1$ 开始进行动态规划，即可得到答案。

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; i++) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, prices[i] + buy1);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, prices[i] + buy2);
        }
        return sell2;
    }
}

lc188. 买卖股票的最佳时机 IV（HD）

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

和上一题类似，但是这次买入卖出次数是不定的

我们用 $buy[i][j]$ 来表示对于数组 $prices[0\dots i]$ 中的价格而言，进行 $j$ 次交易，并且当前手上 还持有一只股票 ，这种情况下的最大利润；用 $sell[i][j]$ 来表示进行 $j$ 次交易，并且当前手上 不持有股票 ，这种情况下的最大利润

对于 $buy[i][j]$ ，我们考虑当前持有的股票是否在第 $i$ 天购入的。如果是，那么在第 $i - 1$ 天时，我们不应该持有股票，对应状态为 $sell[i - 1][j]$ ，并且需要扣除 $prices[i]$ 的购入话费；如果不是，那么在第 $i - 1$ 天时，我们已经持有了股票，对应状态为 $buy[i - 1][j]$ 。由此得到状态转移方程： $buy[i][j] = max{buy[i - 1][j], sell[i - 1][j] - prices[i]}$

同理，对于 $sell[i][j]$ ，如果是第 $i$ 天卖出的，那么在第 $i - 1$ 天时，我们手上持有股票，对于状态 $buy[i - 1][j - 1]$ , 并且需要加入 $prices[i]$ 的卖出收益；如果不是，那么第 $i - 1$ 天时，我们不应该持有股票，对于状态 $sell[i - 1][j]$ 。由此得到状态转移方程 $sell[i][j] = max{sell[i - 1][j], buy[i - 1][j - 1] + prices[i]}$

由于在所有的 $n$ 天结束之后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好，因此最终答案应该是 $sell[n - 1][0\dots k]$ 中的最大值

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];

        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }
        for (int i = 1; i < n; i++) {
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; j++) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }
        return Arrays.stream(sell[n - 1]).max().getAsInt();
    }
}

lc221. 最大正方形（MD）

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

首先，能不能组成正方形主要有两个因素：这个格子的值是否为 ‘1’，以及它左边、上边、左上方的格子的值是否为 ‘1’

我们设 $dp[i][j]$ 表示矩阵中以 $(i, j)$ 作为正方形右下角所能得到的正方形的边长最大值。此时，根据上面提及的两个因素， $dp[i][j]$ 显然受到 $dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]$ 的影响。

由此得到一个状态转移方程： $dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1$

然后就是针对边界情况的处理：对于边界的格子，它只能自己作为一个小正方形（前提是这个格子的值是 ‘1’）。所以对于边界，值为 ‘1’ 的，dp值设置为1

class Solution {
    public int maximalSquare(char[][] matrix) {
        int resLen = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;      
                    }
                }
                resLen = Math.max(resLen, dp[i][j]);
            }
        }
        return resLen * resLen;
    }
}