题解 | #牛群买卖计划II#

知识点：

动态规划/状态机模型

分析：

dp大家都做了好几百遍了，主要分析状态机模型。

比DP更好理解。

首先上图是一个状态转移图，其次再记住买入和卖出算一次买卖

现在分析状态：

状态表示：

f[i][j][k]， k取0或1，0表示手中无货，1表示手中有货，

• f[i][j][0]：第i天，已经进行完j次交易后的最大利润
• f[i][j][1]：第i天，正在进行第j次交易（已经进行了j - 1次交易）后的最大利润

一开始从手中无货开始，首先可以转移到手中有货状态，或者是手中无货状态。同理手中有货也有两种状态转移。

手中无货—>手中无货，则f[i][j][0] = f[i-1][j][0]，直接等于前一天

手中有货-->手中无货，则f[i][j][0] = f[i-1][j][1] + prices[i]， 第i-1天，正在进行第j次交易后的最大利润

f[i][j][0] = max(f[i - 1][j][0], f[i - 1][j][1] + prices[i])

手中有货-->手中有货，则 f[i][j][1] = f[i-1][j][1]

手中无货-->手中有货，则f[i][j][1] = f[i-1][j-1][0] - prices[i] ，这里为什么是j-1呢，是因为进行第j次交易的时候，已经进行了j-1次交易，并且今天再做交易。

f[i][j][1] = max(f[i - 1[j][1], f[i - 1][j - 1][0] - prices[i])

因为都要得到最大利润，所以是都取了max

编程语言：

C++

完整代码：

0 <= k <= 100

0 <= prices.length <= 10000

    static const int N = 10010;
	static const int M = 110;
    int f[N][M][2];
    int maxProfitII(vector<int>& prices, int k) {
        memset(f, -0x3f, sizeof f);
        for(int i = 0;i<=prices.size();i++) f[i][0][0] = 0;
        for(int i =1;i<=prices.size();i++){
            for(int j = 1;j<=k;j++){
                //0->0 1->0
                f[i][j][0] = max(f[i-1][j][0],f[i-1][j][1] + prices[i - 1]);
                //1->1 0->1
                f[i][j][1] = max(f[i-1][j][1],f[i-1][j-1][0] -prices[i-1]);
            }
        }
        int res = 0;
        for (int i = 0; i <= k; i ++ ) res = max(res, f[prices.size()][i][0]);
        return res;
    }

运行时间：11ms 占用内存：9000KB