LeetCode 188. 买卖股票的最佳时机 IV

LeetCode 188. 买卖股票的最佳时机 IV

思路：
如果k > n/2 就相当于交易无限多次了，因为两两组合(买卖)最多 n/2次。
Dp 状态机

代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        const int N = 1e8;
        int n = prices.size();
        int res = 0;
        //可以交易无限多次
        if(k > n/2){
            for(int i = 0;i + 1< n;i++){
                if(prices[i + 1] - prices[i] > 0){
                    res += prices[i + 1] - prices[i];
                }
            }
            return res;
        }
        vector<vector<int>> f(n + 1,vector<int> (k + 1,-N));
        vector<vector<int>> g = f;
        f[0][0] = 0;
        for(int i = 1; i <= n;i++){
            for(int j = 0;j <= k ;j++){
                f[i][j] = max(f[i - 1][j],g[i - 1][j] + prices[i - 1]);
                g[i][j] = g[i - 1][j];
                if(j) g[i][j] = max(g[i][j],f[i - 1][j - 1] - prices[i - 1]);
                res = max(res,f[i][j]);
            }
        }
        return res;
    }
};