买卖股票的最佳时机IV

题目链接

买卖股票的最佳时机 IV

题目描述

注意点

• 1 <= k <= 100
• 1 <= prices.length <= 1000
• 0 <= prices[i] <= 1000
• 不能同时参与多笔交易（必须在再次购买前出售掉之前的股票）
• 最多可以完成 k 笔交易

解答思路

• 本题与买卖股票的最佳时机III类似，区别是最多可以完成k笔交易
• 思路还是与买卖股票的最佳时机III相同，仍然是使用dp[i][j]存储第i天处于第j种状态的最大利润，因为本题最多可以完成k笔交易，所以在任意一天会有k * 2种状态（也就是第k次交易的买入和卖出状态）
• 根据第i - 1天推出第i天所有状态利润的公式也相同：如果处于第j次交易的买入状态，则dp[i][j] = Math.max(dp[i - 1][j], preProfit - prices[i])，其中preProfit是第j - 1次交易后所得的最大利润；如果处于第j次交易的卖出状态，则dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i])，最终找到最后一天所有交易次数的最大利润即可

代码

class Solution {
    public int maxProfit(int k, int[] prices) {
        int res = 0;
        int n = prices.length;
        int[][] dp = new int[n][k * 2];
        for (int j = 0; j < k * 2; j += 2) {
            dp[0][j] = -prices[0];
        }
        for (int i = 1; i < n; i++) {
            int preProfit = 0;
            for (int j = 0; j < k * 2; j += 2) {
                dp[i][j] = Math.max(dp[i - 1][j], preProfit - prices[i]);
                dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
                preProfit = dp[i - 1][j + 1];
            }
        }
        for (int j = 1; j < k * 2; j += 2) {
            res = Math.max(res, dp[n - 1][j]);
        }
        return res;
    }
}

关键点

• 动态规划的思想
• k次交易对应着k次买入和卖出状态