买卖股票问题总结
买卖股票问题是dp的代表类型题目。
- Best Time to Buy and Sell Stock: 这道题看起来很简单，但其实之中蕴含dp的思想。我们可以将问题拆解为两个数组的dp问题：low[i]代表进行到第i天为止的最低股票价格，res[i]代表到第i天为止最大获利。所以
- low[i] = Math.min(low[i], low[i-1])
- res[i] = Math.max(res[i], price[i]-low[i])
当然这道题直接想就可以很简单的做出来，但这种dp的思路很重要。
这道题还可以转化成53题maximum subarray，也就是转化成从第二天开始的profit情况
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int res = 0;
for(int price:prices){
minPrice = Math.min(minPrice, price);
res = Math.max(res, price-minPrice);
}
return res;
}
}
|
- Best Time to Buy and Sell Stock II：这道题有非常非常简单的做法：因为我们有无限次的transaction次数，所以只要后一天的价格比前一天高，我们就买，这非常合理，因为加入我们在买股票也会这么选择。
当然，这道题更重要的一点是它与188题一脉相承，思路非常类似，只不过188相当于多了一个限制条件，所以我们需要转为二维数组，但本质上两道题还是基本一样，dp的思想也非常的值得深思！
- 第i天不卖：dp[i] = dp[i-1]
- 第i天卖，那么可以在前面任意一天买，所以我们需要把这些都算出来求最大值(O(n^2))。然后有一种很巧妙的优化方式(O(n)))，188也用了一样的思路，主要是通过观察迭代方程得到的：dp[i] = max(price[i]-price[m]+dp[m]), m is from 0 to i-1 ===> initalize tempValue = dp[0]-price[0]；dp[i] = price[i] + tempValue;tempValue = max(tempValue, dp[i] - price[i]);
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
| class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
if(n==0)
return 0;
int[] dp = new int[n+1];
int tmp = dp[1] - prices[0];
for(int i =1;i<=dp.length-1;i++){
dp[i] = Math.max(dp[i-1], prices[i-1]+tmp);
tmp = Math.max(tmp, dp[i]-prices[i-1]);
}
return dp[n];
}
}
|
- Best Time to Buy and Sell Stock IV： 有了122的加持，再做188其实就会发现思路完全一样。
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| class Solution {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
if(n==0)
return 0;
if(k>n/2){
return quickSolve(prices);
}
int[][] dp = new int[k+1][n+1];
for(int i =0;i<=k;i++){
dp[i][0] = 0;
}
for(int i = 0;i<=n;i++){
dp[0][i] = 0;
}
for(int i =1;i<=k;i++){
int maxTemp = dp[i][0]-prices[0];
for(int j = 1;j<=n;j++){
int value1 = dp[i][j-1];
int value2 = prices[j-1] + maxTemp;
maxTemp = Math.max(maxTemp, dp[i-1][j]-prices[j-1]);
dp[i][j] = Math.max(value1 , value2);
}
}
return dp[k][n];
}
private int quickSolve(int[] prices){
int ans = 0;
for(int i =1;i<=prices.length-1;i++){
if(prices[i]-prices[i-1]>0)
ans = ans+prices[i]-prices[i-1];
}
return ans;
}
}
|