leetcode 188

问题

Say you have an array for which the i-th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example 1:

1
2
3
Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

1
2
3
4
Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

分析

使用动态规划 $dp[i][j]$ 表示在 $prices[0…j]$ 中进行最多 $i$ 次交易所能获得的最大的利润。

根据在 $prices[j]$ 上的操作，$dp[i][j]$ 的求解可以分为两种情况。

  1. 在 $prices[j]$ 没有出售股票，则 $dp[i][j] = dp[i][j-1]$
  2. 在 $prices[j]$ 出售了股票，假设出售的股票是在 $k (0 \leq k < j)$ 点买入的则 $dp[i][j] = prices[j] - prices[k] + dp[i-1][k-1]$ 。

初始条件：$dp[i][j]$ 的第一维为 0 时，就是说没有进行过交易，那么所能够获得的最大利润自然是 0。$dp[i][j]$ 的第二维为 0 时，那么就是只考虑了 $prices[0]$ ，不可能产生交易，那么所能够获得的最大利润自然也是 0。由上面的分析可以看出，交易 $i$ 次的情况依赖于交易 $i-1$ 次的情况，那么我们可以以最大交易次数来作为DP的阶段。

目标：$dp[k][n-1]$。

不经过优化的代码如代码1所示，时间复杂度为$O(kn^2)$。

经过分析可以看出，最内层循环其实可以降维 $O(1)$ ，令 $maxTmp = dp[i-1][k-1] + prices[k]$ ，而且，$0 \leq k < j$ ，可以在每次迭代 $j$ 的时候（每次迭代结束时）对 $maxTmp$ 进行更新，并初始化 $maxTmp = prices[0]$。

经过优化之后的代码如代码2，时间复杂度 $O(kn)$.

另外，测试集中有k和n相当大的情况。根据贪心算法如果 有 $k >= n/2$ ，就能等同于可以在 $prices$ 进行无限制的买卖了。因此可以先对 k 和 n 之间的大小关系进行判断（否则无法AC）。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k == 0 || n == 0)
            return 0;
        
        if (k >= n/2) {
            int ans = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i-1])
                    ans += prices[i]-prices[i-1];
            }
            return ans;
        }

        vector<vector<int>> dp(k+1, vector<int>(n,0));        
        for (int i = 1; i <= k; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i][j-1];
                for (int k = 0; k < j; ++k) {
                    dp[i][j] = max(dp[i][j], prices[j]-prices[k] + (k>0? dp[i-1][k-1]: 0));
                }
            }
        }
        
        return dp[k][n-1];
        
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k == 0 || n == 0)
            return 0;

        if (k >= n/2) {
            int ans = 0;
            for (int i = 1; i < n; ++i) {
                if (prices[i] > prices[i-1])
                    ans += prices[i]-prices[i-1];
            }
            return ans;
        }

        vector<vector<int>> dp(k+1, vector<int>(n,0));        
        for (int i = 1; i <= k; ++i) {
            int maxTmp = -prices[0];
            for (int j = 1; j < n; ++j) {
                dp[i][j] = max(dp[i][j-1], prices[j]+maxTmp);
                maxTmp = max(maxTmp, dp[i-1][j]-prices[j]);
            }
        }

        return dp[k][n-1];
        
    }
};