买卖股票的最佳时机问题
coconutnut
 2020-02-29 12:51:30      

思路：动态规划

dp[ i ][ j ][ k ]
i - 到第 i 天
j - 最多交易 j 次
k - 0:当前持股 / 1:当前不持股

状态转移方程

1
2
3
4
5
6
7
8
9
10
// 第i天，最多交易j次，当前不持股
dp[i][j][0] = MAX{
	dp[i-1][j][0],                 // 本次不持-上次就不持
	dp[i-1][j-1][1] + 差价          // 本次不持-本次卖
}
// 第i天，最多交易j次，当前持股
dp[i][j][1] = MAX{
	dp[i-1][j][0],                // 本次持-本次买
	dp[i-1][j][1] + 差价           // 本次持-上次就持
}

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int getdp(int i,int j,int k,int[][][] dp,int[] prices){
	if(dp[i][j][k]==-1){
		if(i<1){
			dp[i][j][0]=0;
			dp[i][j][1]=0;
		}else{
			// 本次不持-上次就不持
			int dp1 = getdp(i-1,j,0,dp,prices);
			// 本次不持-本次卖
			int dp2 = j>0 ? getdp(i-1,j-1,1,dp,prices)+prices[i]-prices[i-1] : 0;
			dp[i][j][0] = Math.max(dp1,dp2);
           
			// 本次持-本次买
			int dp3 = getdp(i-1,j,0,dp,prices);
			// 本次持-上次就持
			int dp4 = getdp(i-1,j,1,dp,prices)+prices[i]-prices[i-1];
			dp[i][j][1] = Math.max(dp3,dp4);
            }
        }
	return dp[i][j][k];
}

坑：当k很大时，内存会爆，此时相当于不限制交易次数，直接用贪心解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length<2){
            return 0;
        }

        if(k > prices.length/2){
            // 相当于不限制次数，贪心
            int value = 0;
            for(int i=1;i<prices.length;i++){
                value += prices[i]>prices[i-1] ? prices[i]-prices[i-1] : 0;
            }
            return value;
        }

        int[][][] dp = new int[prices.length][k+1][2];
        for(int i=0;i<prices.length;i++){
            for(int j=0;j<k+1;j++){
                Arrays.fill(dp[i][j],-1);
            }
        }

        return getdp(prices.length-1,k,0,dp,prices);
    }

    public int getdp(int i,int j,int k,int[][][] dp,int[] prices){...}
}

用这一套解法干掉4题

Leetcode 121 买卖股票的最佳时机 —— 最多交易1次
令 k = 1

Leetcode 122 买卖股票的最佳时机 II —— 不限次数
直接贪心

Leetcode 123 买卖股票的最佳时机 III —— 最多交易2次
令 k = 2

Leetcode 188 买卖股票的最佳时机 IV —— 最多交易k次