xiedaxia1hao
commented
3 years ago 188. Best Time to Buy and Sell Stock IV
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Notice that you may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
写代码前先理清楚本题的三个状态，天数、是否持有股票的状态、交易次数。
而对于每种状态，我们又有不同的选择：
天数由prices确定是否持有股票的状态我们可以用0/1表示，0代表不持有股票，1代表持有股票交易次数由k确定
这样我们可以定一个三维dp[i][k][j]数组，其存储的内容是在第i天，我们持有股票的状态为j，已经进行了k次交易时能够获取的最大利润。
这里需要说明的是，第i天和数组的索引一致，它的范围是0 ~ prices.length-1，所以我设置的起点是第0天
比如说dp[5][0][2]：其中存储了 「在第5天时，我们不持有股票，已经进行了2次交易」 时获取的最大利润。
好了，到这里dp的定义和状态我们就确定下来了，那么初始值怎么确定呢？
因为对于第0天来说，它所能够获取的最大利润只有两种，与交易次数毫无关系，所以我们有以下初始值：
1.不持有股票时：dp[0][k][0]=0
2.持有股票时：dp[0][k][1]=-prices[0]
好了，到这里初始值也确定下来了，那么还剩下最后一个问题「状态方程」
我们首先要知道一点，第i天的状态只和第i-1天有关，第i天持有/不持有股票 能够获取的最大利润取决于 第i-1天持有/不持有股票 这里需要注意：我将买入股票时作为一次交易，也就是在买入股票的时候交易次数+1
第i天不持有股票时：
1.如果第i-1天也不持有股票，那就代表状态不变，第i天的状态=第i-1天的状态
2.如果第i-1天持有股票，说明我们在第i天把股票卖了，既然卖股票赚钱了，利润就要多prices[i]
dp[i][k][0] = max(dp[i-1][k][0] , dp[i-1][k][1]+prices[i])
第i天持有股票时：
1.如果第i-1天也持有股票，那就代表状态不变，即dp[i][k][1] = dp[i-1][k][1]
2.如果第i-1天不持有股票，说明我们在第i天买入股票，既然买股票要花钱，利润就要少price[i]
买入股票的同时，当天的交易次数要在前一天的基础上+1
dp[i][k][1] = max(dp[i-1][k][1] , dp[i-1][k-1][0]-prices[i])
还需要注意的点：因为一次交易涉及一天买入一天卖出，一共两天，所以如果k值大于数组长度的一半，k就直接取数组长度的一半，因为多余的交易次数无法达到
即：k=min(k , prices.length/2)
class Solution {
public int maxProfit(int K, int[] prices) {
// Edge Case
if(prices == null || prices.length < 1) {
return 0;
}
int n = prices.length;
K = Math.min(K, n/2);
int[][][] dp = new int[n][K+1][2];
for(int k = 0; k <= K; k++) {
dp[0][k][0] = 0;
dp[0][k][1] = -prices[0];
}
// NOTE: the stating point of i and k has to be 1, as we will need to use i-1 and k-1 inside our loop
for(int i = 1; i < n; i++) {
for(int k = 1; k <= K; k++) {
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
return dp[n-1][K][0];
}
}
Shout out to this post and video for brilliant discussion!