class082 动态规划中用观察优化枚举的技巧-上【算法】

package class082;
// 买卖股票的最佳时机
// 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格
// 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票
// 设计一个算法来计算你所能获取的最大利润
// 返回你可以从这笔交易中获取的最大利润
// 如果你不能获取任何利润，返回 0
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
public class Code01_Stock1 {
  public static int maxProfit(int[] prices) {
    int ans = 0;
    for (int i = 1, min = prices[0]; i < prices.length; i++) {
      // min : 0...i范围上的最小值
      min = Math.min(min, prices[i]);
      ans = Math.max(ans, prices[i] - min);
    }
    return ans;
  }
}

package class082;
// 买卖股票的最佳时机 II
// 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格
// 在每一天，你可以决定是否购买和/或出售股票
// 你在任何时候 最多 只能持有 一股 股票
// 你也可以先购买，然后在 同一天 出售
// 返回 你能获得的 最大 利润
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
public class Code02_Stock2 {
  public static int maxProfit(int[] prices) {
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
      ans += Math.max(prices[i] - prices[i - 1], 0);
    }
    return ans;
  }
}

package class082;
// 买卖股票的最佳时机 III
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii
public class Code03_Stock3 {
  // 完全不优化枚举的方法
  // 通过不了，会超时
  public static int maxProfit1(int[] prices) {
    int n = prices.length;
    // dp1[i] : 0...i范围上发生一次交易，不要求在i的时刻卖出，最大利润是多少
    int[] dp1 = new int[n];
    for (int i = 1, min = prices[0]; i < n; i++) {
      min = Math.min(min, prices[i]);
      dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
    }
    // dp2[i] : 0...i范围上发生两次交易，并且第二次交易在i时刻卖出，最大利润是多少
    int[] dp2 = new int[n];
    int ans = 0;
    for (int i = 1; i < n; i++) {
      // 第二次交易一定要在i时刻卖出
      for (int j = 0; j <= i; j++) {
        // 枚举第二次交易的买入时机j <= i
        dp2[i] = Math.max(dp2[i], dp1[j] + prices[i] - prices[j]);
      }
      ans = Math.max(ans, dp2[i]);
    }
    return ans;
  }
  // 观察出优化枚举的方法
  // 引入best数组，需要分析能力
  public static int maxProfit2(int[] prices) {
    int n = prices.length;
    // dp1[i] : 0...i范围上发生一次交易，不要求在i的时刻卖出，最大利润是多少
    int[] dp1 = new int[n];
    for (int i = 1, min = prices[0]; i < n; i++) {
      min = Math.min(min, prices[i]);
      dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
    }
    // best[i] : 0...i范围上，所有的dp1[i]-prices[i]，最大值是多少
    // 这是数组的设置完全是为了替代最后for循环的枚举行为
    int[] best = new int[n];
    best[0] = dp1[0] - prices[0];
    for (int i = 1; i < n; i++) {
      best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
    }
    // dp2[i] : 0...i范围上发生两次交易，并且第二次交易在i时刻卖出，最大利润是多少
    int[] dp2 = new int[n];
    int ans = 0;
    for (int i = 1; i < n; i++) {
      // 不需要枚举了
      // 因为，best[i]已经揭示了，0...i范围上，所有的dp1[i]-prices[i]，最大值是多少
      dp2[i] = best[i] + prices[i];
      ans = Math.max(ans, dp2[i]);
    }
    return ans;
  }
  // 发现所有更新行为都可以放在一起
  // 并不需要写多个并列的for循环
  // 就是等义改写，不需要分析能力
  public static int maxProfit3(int[] prices) {
    int n = prices.length;
    int[] dp1 = new int[n];
    int[] best = new int[n];
    best[0] = -prices[0];
    int[] dp2 = new int[n];
    int ans = 0;
    for (int i = 1, min = prices[0]; i < n; i++) {
      min = Math.min(min, prices[i]);
      dp1[i] = Math.max(dp1[i - 1], prices[i] - min);
      best[i] = Math.max(best[i - 1], dp1[i] - prices[i]);
      dp2[i] = best[i] + prices[i];
      ans = Math.max(ans, dp2[i]);
    }
    return ans;
  }
  // 发现只需要有限几个变量滚动更新下去就可以了
  // 空间压缩的版本
  // 就是等义改写，不需要分析能力
  public static int maxProfit4(int[] prices) {
    int dp1 = 0;
    int best = -prices[0];
    int ans = 0;
    for (int i = 1, min = prices[0]; i < prices.length; i++) {
      min = Math.min(min, prices[i]);
      dp1 = Math.max(dp1, prices[i] - min);
      best = Math.max(best, dp1 - prices[i]);
      ans = Math.max(ans, best + prices[i]); // ans = Math.max(ans, dp2);
    }
    return ans;
  }
}

package class082;
// 买卖股票的最佳时机 IV
// 给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易
// 也就是说，你最多可以买 k 次，卖 k 次
// 注意：你不能同时参与多笔交易，你必须在再次购买前出售掉之前的股票
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/
public class Code04_Stock4 {
  // 就是股票问题2
  public static int free(int[] prices) {
    int ans = 0;
    for (int i = 1; i < prices.length; i++) {
      ans += Math.max(prices[i] - prices[i - 1], 0);
    }
    return ans;
  }
  public static int maxProfit1(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {
      // 这是一个剪枝
      // 如果k >= n / 2，那么代表所有上坡都可以抓到
      // 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
      return free(prices);
    }
    int[][] dp = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
      for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i][j - 1];
        for (int p = 0; p < j; p++) {
          dp[i][j] = Math.max(dp[i][j], dp[i - 1][p] + prices[j] - prices[p]);
        }
      }
    }
    return dp[k][n - 1];
  }
  public static int maxProfit2(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {
      // 这是一个剪枝
      // 如果k >= n / 2，那么代表所有上坡都可以抓到
      // 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
      return free(prices);
    }
    int[][] dp = new int[k + 1][n];
    for (int i = 1, best; i <= k; i++) {
      best = dp[i - 1][0] - prices[0];
      for (int j = 1; j < n; j++) {
        // 用best变量替代了枚举行为
        dp[i][j] = Math.max(dp[i][j - 1], best + prices[j]);
        best = Math.max(best, dp[i - 1][j] - prices[j]);
      }
    }
    return dp[k][n - 1];
  }
  // 对方法2进行空间压缩的版本
  public static int maxProfit3(int k, int[] prices) {
    int n = prices.length;
    if (k >= n / 2) {
      // 这是一个剪枝
      // 如果k >= n / 2，那么代表所有上坡都可以抓到
      // 所有上坡都可以抓到 == 交易次数无限，所以回到股票问题2
      return free(prices);
    }
    int[] dp = new int[n];
    for (int i = 1, best, tmp; i <= k; i++) {
      best = dp[0] - prices[0];
      for (int j = 1; j < n; j++) {
        tmp = dp[j];
        dp[j] = Math.max(dp[j - 1], best + prices[j]);
        best = Math.max(best, tmp - prices[j]);
      }
    }
    return dp[n - 1];
  }
}

package class082;
// 买卖股票的最佳时机含手续费
// 给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格
// 整数 fee 代表了交易股票的手续费用
// 你可以无限次地完成交易，但是你每笔交易都需要付手续费
// 如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
// 返回获得利润的最大值
// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
public class Code05_Stack5 {
  public static int maxProfit(int[] prices, int fee) {
    // prepare : 交易次数无限制情况下，获得收益的同时扣掉了一次购买和手续费之后，最好的情况
    int prepare = -prices[0] - fee;
    // done : 交易次数无限制情况下，能获得的最大收益
    int done = 0;
    for (int i = 1; i < prices.length; i++) {
      done = Math.max(done, prepare + prices[i]);
      prepare = Math.max(prepare, done - prices[i] - fee);
    }
    return done;
  }
}

package class082;
// 买卖股票的最佳时机含冷冻期
// 给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格
// 设计一个算法计算出最大利润
// 在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
// 测试链接 : https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
public class Code06_Stack6 {
  public static int maxProfit1(int[] prices) {
    int n = prices.length;
    if (n < 2) {
      return 0;
    }
    // prepare[i] : 0...i范围上，可以做无限次交易，获得收益的同时一定要扣掉一次购买，所有情况中的最好情况
    int[] prepare = new int[n];
    // done[i] : 0...i范围上，可以做无限次交易，能获得的最大收益
    int[] done = new int[n];
    prepare[1] = Math.max(-prices[0], -prices[1]);
    done[1] = Math.max(0, prices[1] - prices[0]);
    for (int i = 2; i < n; i++) {
      done[i] = Math.max(done[i - 1], prepare[i - 1] + prices[i]);
      prepare[i] = Math.max(prepare[i - 1], done[i - 2] - prices[i]);
    }
    return done[n - 1];
  }
  // 只是把方法1做了变量滚动更新(空间压缩)
  // 并没有新的东西
  public static int maxProfit2(int[] prices) {
    int n = prices.length;
    if (n < 2) {
      return 0;
    }
    // prepare : prepare[i-1]
    int prepare = Math.max(-prices[0], -prices[1]);
    // done2 : done[i-2]
    int done2 = 0;
    // done1 : done[i-1]
    int done1 = Math.max(0, prices[1] - prices[0]);
    for (int i = 2, curDone; i < n; i++) {
      // curDone : done[i]
      curDone = Math.max(done1, prepare + prices[i]);
      // prepare : prepare[i-1] -> prepare[i]
      prepare = Math.max(prepare, done2 - prices[i]);
      done2 = done1;
      done1 = curDone;
    }
    return done1;
  }
}

package class082;
// DI序列的有效排列
// 给定一个长度为n的字符串s，其中s[i]是:
// "D"意味着减少，"I"意味着增加
// 有效排列是对有n+1个在[0,n]范围内的整数的一个排列perm，使得对所有的i：
// 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]
// 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]
// 返回有效排列的perm的数量
// 因为答案可能很大，所以请返回你的答案对10^9+7取余
// 测试链接 : https://leetcode.cn/problems/valid-permutations-for-di-sequence/
public class Code07_DiSequence {
  public static int numPermsDISequence1(String s) {
    return f(s.toCharArray(), 0, s.length() + 1, s.length() + 1);
  }
  // 猜法很妙！
  // 一共有n个数字，位置范围0~n-1
  // 当前来到i位置，i-1位置的数字已经确定，i位置的数字还没确定
  // i-1位置和i位置的关系，是s[i-1] : D、I
  // 0~i-1范围上是已经使用过的数字，i个
  // 还没有使用过的数字中，比i-1位置的数字小的，有less个
  // 还没有使用过的数字中，比i-1位置的数字大的，有n - i - less个
  // 返回后续还有多少种有效的排列
  public static int f(char[] s, int i, int less, int n) {
    int ans = 0;
    if (i == n) {
      ans = 1;
    } else if (i == 0 || s[i - 1] == 'D') {
      for (int nextLess = 0; nextLess < less; nextLess++) {
        ans += f(s, i + 1, nextLess, n);
      }
    } else {
      for (int nextLess = less, k = 1; k <= n - i - less; k++, nextLess++) {
        ans += f(s, i + 1, nextLess, n);
      }
    }
    return ans;
  }
  public static int numPermsDISequence2(String str) {
    int mod = 1000000007;
    char[] s = str.toCharArray();
    int n = s.length + 1;
    int[][] dp = new int[n + 1][n + 1];
    for (int less = 0; less <= n; less++) {
      dp[n][less] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
      for (int less = 0; less <= n; less++) {
        if (i == 0 || s[i - 1] == 'D') {
          for (int nextLess = 0; nextLess < less; nextLess++) {
            dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
          }
        } else {
          for (int nextLess = less, k = 1; k <= n - i - less; k++, nextLess++) {
            dp[i][less] = (dp[i][less] + dp[i + 1][nextLess]) % mod;
          }
        }
      }
    }
    return dp[0][n];
  }
  // 通过观察方法2，得到优化枚举的方法
  public static int numPermsDISequence3(String str) {
    int mod = 1000000007;
    char[] s = str.toCharArray();
    int n = s.length + 1;
    int[][] dp = new int[n + 1][n + 1];
    for (int less = 0; less <= n; less++) {
      dp[n][less] = 1;
    }
    for (int i = n - 1; i >= 0; i--) {
      if (i == 0 || s[i - 1] == 'D') {
        dp[i][1] = dp[i + 1][0];
        for (int less = 2; less <= n; less++) {
          dp[i][less] = (dp[i][less - 1] + dp[i + 1][less - 1]) % mod;
        }
      } else {
        dp[i][n - i - 1] = dp[i + 1][n - i - 1];
        for (int less = n - i - 2; less >= 0; less--) {
          dp[i][less] = (dp[i][less + 1] + dp[i + 1][less]) % mod;
        }
      }
    }
    return dp[0][n];
  }
}