买卖股票的最佳时机I
121. 买卖股票的最佳时机I-LeetCode题目地址
这道题题目要求我们在某一天买入股票，在未来的某一天卖出股票，也就是只能买卖一次股票，我们可以从左到右遍历整个数组，维护一个最小值，最小值代表的是第i天之前股票的最小值，不断计算今天股票的价格和之前天数当中股票最小值的差值，找出最大值返回结果，Java版代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] > min) {
maxProfit = Math.max(maxProfit, prices[i] - min);
}
min = Math.min(min, prices[i]);
}
return maxProfit;
}
}
|
买卖股票的最佳时机II
122. 买卖股票的最佳时机 II-LeetCode题目地址
记忆化搜索
这道题和上到题有所不同，我们可以多次买卖股票，因此就需要进行动态规划了，具体情况分为今天是否有股票，今天没有股票（买还是不买），今天有股票（卖还是不卖），并且如果最后一天持有股票一定要卖。
由于递归时间复杂度很高，因此我们引入记忆化搜索减少重复的递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int maxProfit(int[] prices) {
int[][] memo = new int[prices.length][2];
for (int[] ints : memo) {
Arrays.fill(ints, -1);
}
return dfs(prices,0,0,memo);
}
public int dfs(int[] prices,int i,int hold,int[][] memo) {
if(i == prices.length) return 0;
if(memo[i][hold] != -1) return memo[i][hold];
if(hold == 0){
return memo[i][hold] = Math.max(dfs(prices,i+1,0,memo),dfs(prices,i+1,1,memo) - prices[i]);
}
if (i == prices.length-1) return memo[i][hold] = dfs(prices,i+1,0,memo) + prices[i];
return memo[i][hold] = Math.max(dfs(prices,i+1,1,memo),dfs(prices,i+1,0,memo) + prices[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
26
27
| class Solution {
private int[] prices;
private int[][] memo;
public int maxProfit(int[] prices) {
this.prices = prices;
int n = prices.length;
memo = new int[n][2];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(n - 1, 0);
}
private 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 - 1, 0) - prices[i]);
}
return memo[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);
}
}
|
1:1翻译为递推
我们根据这两个式子memo[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);和memo[i][hold] = Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);一比一翻译为递推，Java版代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length+1][2];
dp[1][1] = -prices[0];
for (int i = 2; i <= prices.length; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i-1]);
}
return dp[prices.length][0];
}
}
|
空间复杂度优化
上面我们用了一个数组来记录一天内是否持有股票的利润最大值，但是在递推的过程中我们只用到了前一天的状态，因此可以优化空间复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int maxProfit(int[] prices) {
int f0 = 0;
int f1 = -prices[0];
for (int i = 2; i <= prices.length; i++) {
int f = f0;
f0 = Math.max(f0, f1 + prices[i-1]);
f1 = Math.max(f1, f - prices[i-1]);
}
return f0;
}
}
|
买卖股票的最佳时机含冷冻期
309. 买卖股票的最佳时机含冷冻期-LeetCode题目地址
记忆化搜索
这道题在112的基础上加上了一个冷静期，在冷静期中我们什么也干不了，因此正着递归只需要加上冷静期的判断即可
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
| class Solution {
public int maxProfit1(int[] prices) {
int[][] memo = new int[prices.length][2];
for (int[] ints : memo) {
Arrays.fill(ints, -1);
}
return dfs(prices,0,0,memo,false);
}
public int dfs(int[] prices,int i,int hold,int[][] memo,boolean isCool) {
if(i == prices.length) return 0;
if(isCool){
return dfs(prices,i+1,hold,memo,false);
}
if(memo[i][hold] != -1) return memo[i][hold];
if(hold == 0){
return memo[i][hold] = Math.max(dfs(prices,i+1,0,memo,false),dfs(prices,i+1,1,memo,false) - prices[i]);
}
if (i == prices.length-1) return memo[i][hold] = dfs(prices,i+1,0,memo,true) + prices[i];
return memo[i][hold] = Math.max(dfs(prices,i+1,1,memo,false),dfs(prices,i+1,0,memo,true) + prices[i]);
}
}
|
倒着递归，当天持有股票可能是昨天有，或者今天刚买（如果是今天刚买，那么上一天既不能买，也不能卖，那么只能从i-2天没有持有股票的状态转移过来），当天没有股票可能是上一天没有股票或者今天刚刚卖了股票
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 {
private int[] prices;
private int[][] memo;
public int maxProfit(int[] prices) {
this.prices = prices;
int n = prices.length;
memo = new int[n][2];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(n - 1, 0);
}
private 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:1翻译为递推
根据memo[i][hold] = Math.max(dfs(i - 1, 1), dfs(i - 2, 0) - prices[i]);和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
| class Solution {
public int maxProfit(int[] prices) {
int[][] dp = new int[prices.length+1][2];
dp[1][1] = -prices[0];
for (int i = 2; i <= prices.length; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i-1]);
}
return dp[prices.length][0];
}
}
|
空间复杂度优化
我们计算当天的最优解时候需要知道前一天的值和i-2天没有持有股票的值，因此优化如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public int maxProfit(int[] prices) {
int f0 = 0;
int ff0 = 0;
int ff1 = -prices[0];
for (int i = 2; i <= prices.length; i++) {
int f = ff0;
ff0 = Math.max(ff0, ff1 + prices[i-1]);
ff1 = Math.max(ff1, f0 - prices[i-1]);
f0 = f;
}
return ff0;
}
}
|
