动态规划-状态机（188. 买卖股票的最佳时机 IV）-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划-状态机（188. 买卖股票的最佳时机 IV）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

状态分类：

f[i,j,0]考虑前i只股票，进行了j笔交易，目前未持有股票所能获得最大利润

f[i,j,1]考虑前i只股票，进行了j笔交易，目前持有股票所能获得最大利润

状态转移：

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

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

动态规划-状态机（188. 买卖股票的最佳时机 IV）,算法笔记,动态规划,算法

class Solution {
    static int INF = 0x3f3f3f3f;
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int f[][][] = new int[n+1][k+1][2];
        for(int i = 0;i <= n;i++){
            for(int j = 0;j <= k;j++){
                Arrays.fill(f[i][j],-INF);
            }
            
        }
        for(int i = 0;i <= n;i++)f[i][0][0] = 0;

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= k;j++){
                f[i][j][0] = Math.max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);
                f[i][j][1] = Math.max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);
            }
        }
        int ans = 0;
        for(int i = 0;i <= k;i++){
            ans = Math.max(ans,f[n][i][0]);
        }
        return ans;
    }
}

还有一位大佬的看不懂的极妙解法--滚动的dp？文章来源地址https://www.toymoban.com/news/detail-719156.html

// java
class Solution {
    public int maxProfit(int k, int[] prices) {
        int[] buy = new int[k], sell = new int[k];
        Arrays.fill(buy, -prices[0]);
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0, pre = 0; j < k; j++) {
                buy[j] = (pre = Math.max(buy[j], pre - prices[i]));
                sell[j] = (pre = Math.max(sell[j], pre + prices[i]));
            }
        }
        return Math.max(sell[k - 1], 0);
    }
}

到了这里，关于动态规划-状态机（188. 买卖股票的最佳时机 IV）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！