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

题目考察的知识点：动态规划

题目解答方法的文字分析：f数组表示买入状态时的最大利润，g数组表示卖出状态时的最大利润，可以交易k次，所以创建一个k+1乘n的数组；f，g为dp表，然后初始化dp表；填表，返回k+1种交易次数中利润最大的。

本题解析所用的编程语言：c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型vector 
     * @param k int整型 
     * @return int整型
     */
    const int INF = 0x3f3f3f3f;
    int maxProfitII(vector<int>& prices, int k) {
        // write code here
        if (k == 0)
            return 0;
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -INF)), g(n, vector<int>(k + 1, -INF));
        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < k + 1; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                if (j >= 1)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
                else 
                    g[i][j] = g[i - 1][j];
            }
        }
        int ret = 0;
        for (int j = 0; j < k + 1; ++j)
            ret = max(ret, g[n - 1][j]);
        return ret;
    }
};