买卖股票的最佳时机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;}
}