leetcode-zgd-day50-123.买卖股票的最佳时机III/188.买卖股票的最佳时机IV/764.最大加号标志

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

题目链接：123. 买卖股票的最佳时机 III - 力扣（Leetcode）

解题思路：

这个题最关键的地方就是需要搞清楚一共有多少种状态，该题目中的状态分为5种也可以，分成4种也可以，分为5种就是把第一次买入股票之前的状态也单独分为了一个状态。

然后就是根据状态来构造dp数组，以及递推关系式

还需要注意的是，因为题目没有限制不可以同一天买入卖出，所以理论上可以同一天买入卖出很多次。这就是在初始化的时候，dp(0,2)也要初始化为-price[0]的原因。

 class Solution {
     public int maxProfit(int[] prices) {
         /**
          * 最多可以完成两笔交易，那么状态就有 0.第一次持有 1.第二次未持有 2.第二次持有 3.第二次卖出
          * dp[i][j] 第i天状态为j时的最大利润
          * dp[i][0] = Math.max(-prices[i],dp[i - 1][0])
          * dp[i][1] = Math.max(dp[i - 1][1], d[i - 1][0] + prices[i])
          * dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i])
          * dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i])
          * 初始化 dp[0][0] = -prices[0]
          */
         int[][] dp= new int[prices.length][4];
         dp[0][0] = -prices[0];
         dp[0][2] = -prices[0]; // 可以在同一天买入卖出,所以这种情况是存在的
         for (int i = 1; i < prices.length; i++) {
             dp[i][0] = Math.max(-prices[i], dp[i - 1][0]);
             dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
             dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
             dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
             System.out.println(dp[i][0] + " " + dp[i][1] + " " + dp[i][2] + " " + dp[i][3]);
         }
         return dp[prices.length - 1][3];
     }
 }

188.买卖股票的最佳时机IV

题目链接：188. 买卖股票的最佳时机 IV - 力扣（Leetcode）

解题思路：

这个题目其实跟上一个题目是完全相同的，只不过是状态变更多了，需要用for循环的方式进行抽象了。递推关系式、初始化的方式以及循环方式都是一样的。

 class Solution {
     public int maxProfit(int k, int[] prices) {
         /**
          * 最多可以完成两笔交易，那么状态就有 0.第一次持有 1.第二次未持有 2.第二次持有 3.第二次卖出 2k-2. 第k次持有  2k-1. 第k次未持有
          * dp[i][j] 第i天状态为j时的最大利润
          * dp[i][0] = Math.max(-prices[i],dp[i - 1][0])
          * dp[i][1] = Math.max(dp[i - 1][1], d[i - 1][0] + prices[i])
          * dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] - prices[i])
          * dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i])
          * 初始化 dp[0][0] = -prices[0]
          */
         int[][] dp= new int[prices.length][2 * k];
         for(int i = 0; i < k; i++){
             dp[0][2 * i] = -prices[0]; // 第k次持有 都需要初始化
         }
         for (int i = 1; i < prices.length; i++) {
             for(int j = 0; j < 2 * k; j++){
                 if(j == 0){
                     dp[i][j] = Math.max(-prices[i], dp[i - 1][j]);
                 } else if(j % 2 == 0){
                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                 } else {
                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                 }
             }
         }
         return dp[prices.length - 1][2 * k - 1];
     }
 }

764.最大加号标志

题目链接：764. 最大加号标志 - 力扣（Leetcode）

解题思路：

改题目其实可以拆分一一下，就是分成横向和纵向去考虑最大加号标志的长度。这个横向和纵向还可以继续细分，也就是上下左右。在某个点向上下左右四个方向延申，取四个方向最短的那个方向的长度，就是当前结点的最大加号的大小。根据这个思路，可以创建四个dp数组，分别计算四个不同方向上最长的延伸长度，然后每个结点再根据四个dp数组取最小值。这样做的缺点就是浪费空间，用一个dp数组就可以解决的问题，却浪费了四份空间。

 class Solution {
     public int orderOfLargestPlusSign(int n, int[][] mines) {
         /*
         动态规划
         dp[i][j] 已当前元素为中心能够构成的最大加号大小
         分四个维度对这个dp数组进行维护，也就是说从头至尾需要对dp数组更新四次,按照上下左右的顺序
         dp[i][j] =  if(mines[i][j] == 0) 0
                     else dp[i - 1][j] + 1;
          */
         int[][][] dp = new int[n][n][4];
         Set<Integer> record = new HashSet<>();
         for(int[] m : mines){
             if(!record.contains(m[0] * n + m[1])) record.add(m[0] * n + m[1]);
         }
         for(int i = 0; i < n; i++){
             for(int j = 0; j < n; j++){
                 Arrays.fill(dp[i][j],n);
             }
         }
         for(int i = 0; i < n; i++){
             for(int j = 0; j < n; j++){
                 if(record.contains(i * n + j)){ // 当前就是边界外
                     dp[i][j][0] = 0;
                     dp[i][j][1] = 0;
                 }else{
                     if(i == 0) dp[i][j][0] = 1;
                     else dp[i][j][0] = dp[i - 1][j][0] + 1;
                     if(j == 0) dp[i][j][1] = 1;
                     else dp[i][j][1] = dp[i][j - 1][1] + 1;
                 }
             }
         }
         for(int i = n - 1; i >= 0; i--){
             for(int j = n - 1; j >= 0; j--){
                 if(record.contains(i * n + j)){ // 当前就是边界外
                     dp[i][j][2] = 0;
                     dp[i][j][3] = 0;
                 }else{
                     if(i == n - 1) dp[i][j][2] = 1;
                     else dp[i][j][2] = dp[i + 1][j][2] + 1;
                     if(j == n - 1) dp[i][j][3] = 1;
                     else dp[i][j][3] = dp[i][j + 1][3] + 1;
                 }
             }
         }
         int ans = 0;
         for(int i = 0; i < n; i++){
             for(int j = 0; j < n; j++){
                 int minSize = Math.min(Math.min(dp[i][j][0],dp[i][j][1]),Math.min(dp[i][j][2],dp[i][j][3]));
                 ans = Math.max(ans,minSize);
             }
         }
         return ans;
     }
 }

优化：只是用一个dp数组

这个解法的关键在于，count变量，这个变量非常重要，要用这个变脸和dp(i,j)进行比较，而不可以直接用dp数组里的值，比如dp(i-1，j)，因为如果直接用dp数组里的值，各个方向之间就会互相影响。

 class Solution {
     public int orderOfLargestPlusSign(int n, int[][] mines) {
         int[][] dp = new int[n][n];
         Set<Integer> record = new HashSet<>();
         for(int[] m : mines){
             if(!record.contains(m[0] * n + m[1])) record.add(m[0] * n + m[1]);
         }
         for(int i = 0; i < n; i++){
             Arrays.fill(dp[i],n);
         }
         int ans = 0;
         int count = 0;
         for(int i = 0; i < n; i++){
             count = 0;
             for(int j = 0; j < n; j++){
                 if(record.contains(i * n + j)){ // 当前就是边界外
                      count = 0;
                 }
                 else count++;
                 dp[i][j] = Math.min(count, dp[i][j]);
             }
             count = 0;
             for(int j = n - 1; j >= 0; j--){
                 if(record.contains(i * n + j)){ // 当前就是边界外
                     count = 0;
                 }
                 else count++;
                 dp[i][j] = Math.min(count, dp[i][j]);
             }
         }
         //i是列 j是行
         for(int i = 0; i < n; i++){
             count = 0;
             for(int j = 0; j < n; j++){
                 if(record.contains(j * n + i)){ // 当前就是边界外
                     count = 0;
                 }
                 else count++;
                 dp[j][i] = Math.min(count, dp[j][i]);
             }
             count = 0;
             for(int j = n - 1; j >= 0; j--){
                 if(record.contains(j * n + i)){ // 当前就是边界外
                     count = 0;
                 }
                 else count++;
                 dp[j][i] = Math.min(count, dp[j][i]);
                 ans = Math.max(ans,dp[j][i]);
             }
         }
         return ans;
     }
 }