动态规划 + 贪心

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/

  • 最多只能做k次交易
  • 不是说正好k次，而是k次以内的交易都行， 哪个最优
  • 有个大过滤，如果K > N/2， 就等于无限次交易

为啥？

  • 无限次交易的实质就是把每个上坡都求出来

image.png

  • 整个数组最多上坡数也不会超过N/2, 看最频繁的

image.png

  • 那么如果K > N/2了，也就相当于做无限次交易求最优了嘛，也就是122题买卖股票最佳时机Ⅱ
    • 问题Ⅱ是把一个上坡分解成了多次算，我们也可以不分解呀
      • 一个上坡上的多次交易是可以合成一笔交易的
  • 所以我们接下来就讨论 K < N/2的情况

dp[ i ][ j ]含义： arr[0~i] 交易次数不超过j 次的最优
image.png

dp[ i ][ j ]
1) [ i ]不参加任何交易
dp[i - 1][ j ]

2) [ i ]参加交易
这里有一个贪心，就是i位置除了最后一次交易卖出时机之外其他都不考虑，
image.png
比如此时j = 3， i是第二次交易，那么第3次交易就废了呀，你第三次只能在i位置买入再卖出，第三次收益0
也就是i参加了前面的交易，那么后面的交易其实就废了。
所以这里的参加交易指的是参加最后一次交易的卖出时机，那么就可以细分了

  • ① 最后一次交易的买入时机在[ i ]

0~i 上做 k- 1次交易 + [i] - [i]

  • ② 最后一次交易的买入时机在[ i - 1]

0~i-1 上做 k-1次交易 + [ i ] - [i - 1]

  • ③ 最后一次交易的买入时机在[ i - 2]

0~i-2 上做 k-1 次交易 + [ i ] - [i - 2]

  • ④ 最后一次交易的买入时机在[ i - 3]

……..
枚举所有情况

综上
image.png

有枚举行为，可以斜率优化
image.png

  • 在求dp[5][2]的时候， ②到⑥可能性其实可以看作方框内的[5]先不加， 它们6个人pk出一个max之后，这个max再去+[5]

  • 然后我们再看dp[6][2]的时候，把[6]抠了，可以发现之前这些指标已经枚举过一次了

    • image.png
    • 也就是 dp [ i ] [ j ] 的求解过程能加速 dp [ i + 1 ] [ j ] 的求解过程

  • 写得清晰一点，这样看

    • image.png

  • 未优化版本

    1.  public int maxProfit1(int k, int[] prices) {
    2.       if (prices == null || prices.length == 0) {
    3.           return 0;
    4.       }
    5.       int N = prices.length;
    6.       if (k >= N / 2) {
    7.           int ans = 0;
    8.           for (int i = 1; i < prices.length; i++) {
    9.               ans += Math.max(prices[i] - prices[i - 1], 0);
    10.           }
    11.           return ans;
    12.       }
    14.       int[][] dp = new int[N][k + 1];
    15.       for (int i = 1; i < N; i++) {
    16.           for (int j = 1; j <= k; j++) {
    17.               dp[i][j] = dp[i - 1][j];
    18.               for (int p = 0; p <= i; p++) {
    19.                   dp[i][j] = Math.max(dp[i][j], dp[p][j - 1] + prices[i] - prices[p]);
    20.               }
    21.           }
    22.       }
    23.       return dp[N - 1][k];
    24.   }

  • 优化版本

    1. public int maxProfit(int k, int[] prices) {
    2.   if (prices == null || prices.length == 0) {
    3.       return 0;
    4.   }
    5.   int N = prices.length;
    6.   int ans = 0;
    7.   if (k >= N / 2) {
    8.       for (int i = 1; i < prices.length; i++) {
    9.           ans += Math.max(prices[i] - prices[i - 1], 0);
    10.       }
    11.       return ans;
    12.   }
    14.   int[][] dp = new int[N][k + 1];
    15.   for (int j = 1; j <= k; j++) {
    16.       int best = dp[0][j - 1] - prices[0];
    17.       for (int i = 1; i < N; i++) {
    18.           dp[i][j] = Math.max(dp[i - 1][j], prices[i] + best);
    19.           best = Math.max(best, dp[i][j - 1] - prices[i]);
    20.       }
    21.   }
    22.   return dp[N - 1][k];
    23. }