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

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

思路：

    分别表示天数，购买次数，是否持有股票
    为了方便表示边界，
    将n范围设为1-n。
    将k范围设为1-k+1。注意1表示零次
    	dp[i+1][k][0] = max(dp[i][k][0], dp[i][k-1][1]+prices[i])
    	dp[i+1][k][1] = max(dp[i][k][1], dp[i][k][0]-prices[i])      
1
2
3
4
5
6

class Solution {
    public int maxProfit(int k, int[] prices) {

        int n = prices.length;
        int[][][] dp = new int[n+1][k+2][2];
        for(int i=0; i<n+1; i++) {
            for(int j=0; j<k+2; j++) {
                Arrays.fill(dp[i][j], Integer.MIN_VALUE/2);
            }
        }        
        for(int j=1; j<k+2; j++) {
            dp[0][j][0] = 0;
        }
        for(int i=0; i<n; i++) {
            for(int j=1; j<k+2; j++) {
                dp[i+1][j][0] = Math.max(dp[i][j][0], dp[i][j-1][1]+prices[i]);
                dp[i+1][j][1] = Math.max(dp[i][j][1], dp[i][j][0]-prices[i]);
            }
        }
        return dp[n][k+1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22