典型dp—股票问题
# 121. 买卖股票的最佳时机 (opens new window)
class Solution {
public int maxProfit(int[] prices) {
int ret = 0;
int min = Integer.MAX_VALUE;
for(int i=0;i<prices.length;i++){
min = Math.min(min,prices[i]);
ret = Math.max(prices[i]-min,ret);
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 122. 买卖股票的最佳时机 II (opens new window)
不限制交易次数；
递归边界：
dfs(-1,0)=0 第 0天开始未持有股票利润为 0；
dfs(-1,1)=-∞ 第 0天开始不可能持有股票；
递推关系：
动态规划：
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n+1][2];
dp[0][1] = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
dp[i+1][0] = Math.max(dp[i][0],dp[i][1]+prices[i]);
dp[i+1][1] = Math.max(dp[i][1],dp[i][0]-prices[i]);
}
return dp[n][0];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
记忆化搜索：
class Solution {
int[] prices;
int[][] memo;
public int maxProfit(int[] prices) {
this.prices = prices;
int n = prices.length;
this.memo = new int[n][2];
for(int i=0;i<n;i++){
Arrays.fill(memo[i],-1);
}
return dfs(n-1,0);
}
int dfs(int i,int state){
if(i<0)
return state==1?Integer.MIN_VALUE:0;
if(memo[i][state]!=-1)
return memo[i][state];
if(state==1)
return memo[i][state] = Math.max(dfs(i-1,1),dfs(i-1,0)-prices[i]);
return memo[i][state] = Math.max(dfs(i-1,0),dfs(i-1,1)+prices[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 309. 买卖股票的最佳时机含冷冻期 (opens new window)
动态规划：
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n+2][2];
dp[1][1] = Integer.MIN_VALUE;
for(int i=0;i<n;i++){
dp[i+2][1] = Math.max(dp[i][0]-prices[i],dp[i+1][1]);
dp[i+2][0] = Math.max(dp[i+1][1]+prices[i],dp[i+1][0]);
}
return dp[n+1][0];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
记忆化搜索：
class Solution {
int[] prices;
int[][] memo;
public int maxProfit(int[] prices) {
this.prices = prices;
int n = prices.length;
memo = new int[n][2];
for (int i = 0; i < n; i++)
Arrays.fill(memo[i], -1);
return dfs(n - 1, 0);
}
int dfs(int i, int hold) {
if (i < 0)
return hold == 1 ? Integer.MIN_VALUE : 0;
if (memo[i][hold] != -1)
return memo[i][hold];
if (hold == 1)
return memo[i][hold] = Math.max(dfs(i-1,1),dfs(i-2,0)-prices[i]);
return memo[i][hold] = Math.max(dfs(i-1,0),dfs(i-1,1)+prices[i]);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 188. 买卖股票的最佳时机 IV (opens new window)
状态定义：dfs(i,j,0)表示到第 i 天结束完成至多 j 笔交易，未持有股票最大利润；
递归边界：
dfs(·,-1,·)=-∞，j不可能为负；
dfs(-1,j,0)=0，第0天未持有股票，利润为0；
dfs(-1,j,1)=-∞，第0天不可能持有股票；
递推关系：
class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
int[][][] dp = new int[n+1][k+2][2];//k次说明可以0~k次，还有一次初始状态-1；
for(int i=0;i<n;i++){
for(int j=0;j<k+2;j++){
Arrays.fill(dp[i][j],Integer.MIN_VALUE/2);//防止溢出
}
}
//次数不可能为负，多加了一个维度表示负，所以从1开始
for(int j=1;j<k+2;j++){
dp[0][j][0] = 0;
}
for(int i=0;i<n;i++){
for(int j=0;j<k+1;j++){
dp[i+1][j+1][0] = Math.max(dp[i][j+1][0],dp[i][j+1][1]+prices[i]);
dp[i+1][j+1][1] = Math.max(dp[i][j+1][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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
题意改为恰好完成 k笔交易：
递归到 i<0，只有 j=0合法，只需要更改dp[0][1][0]=0;