动态规划之买卖股票系列

在leetcode上有一些系列的题目,题目比较类似,只是区别于有一些细节条件不同,难度也是从易到难不断升级,这类题目一个系列做下来,非常锻炼人的思维能力。

今天看看可以使用动态规划解决的买卖股票这个系列。

买卖股票的最佳时机(只能买卖一次)

1

对于每一天,有两种状态:

  1. 持有股票,可能是之前买的,也可能是当天买的。反正就是之前买过,但没有卖出。
  2. 不持有股票,可能之前就没买,或者已经卖了。

我们定义 dp[i][0] 表示第i天持有股票的收益, dp[i][1] 表示第i天未持有股票的收益。

对于持有股票而言,有可能是前一天持有股票,一直到今天。又或者是前一天未持有股票,当天买入的。
所以,对于持有股票的状态,会有 dp[i][0]=max(dp[i-1][0], -prices[i])

这里为什么是-prices[i],而不是 dp[i-1][1]-prices[i]?
因为本题只允许买卖一次,既然是当天买的,那么前一天收益必然为0

对于未持有股票而言,有可能是前一天就未持有,一直到当天。也有可能是前一天持有股票,当天卖出的。
所以,对于未持有股票而言,状态为: dp[i][1]=max(dp[i-1][1], dp[i-1][0]+prices[i])

所以最终的状态转移公式为:

1
2
3
|-- dp[i][0]=max(dp[i-1][0], -prices[i]), 持有股票
|
|-- dp[i][1]=max(dp[i-1][1], dp[i-1][0]+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
function maxProfit(prices: number[]): number {
const length = prices.length;
const dp = new Array(length).fill(0).map(() => new Array(2).fill(0));

// 初始化状态
dp[0] = [-prices[0], 0];

for (let i = 1; i < length; i++) {
// 当天持有股票
// 前一天持有,或前一天未持有,当天买入
dp[i][0] = Math.max(
dp[i - 1][0],
// 由于只能买卖一次,当天买入的,前一天未持有,前一天收益为0
0 - prices[i]
);

// 当天未持有股票
// 前一天未持有,或前一天持有,当天卖出
dp[i][1] = Math.max(
dp[i - 1][1],
dp[i - 1][0] + prices[i]
);
}

return dp[length - 1][1];
}

除了上面的状态定义方式,还可以根据买入卖出定义状态,即只买卖一次。是【买卖股票的最佳时机IV(最多买卖k次)】的一个特殊变种,k=1,只买卖一次。
具体思路及代码可参考【买卖股票的最佳时机IV(最多买卖k次)】

当然,除了动态规划,本题也可以使用贪心算法。

1
2
3
4
5
6
7
8
9
10
11
12
function maxProfit(prices: number[]): number {

let minPrice = Number.MAX_VALUE;
let maxProfit = 0;

for (const p of prices) {
minPrice = Math.min(minPrice, p);
maxProfit = Math.max(maxProfit, p - minPrice);
}

return maxProfit;
}

买卖股票的最佳时机II(可以买卖多次)

2

本题是上面的升级,由只允许买卖一次变为允许买卖多次,但只允许持有一只股票。

状态定义和上题一模一样。只不过状态转移公式变一下。

由于可以允许买卖多次,因此,当第i天持有股票时,如果前一天未持有,则前一天的利润不再是0,而是 dp[i-1][1]。

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
function maxProfit(prices: number[]): number {
const length = prices.length;
const dp = new Array(length).fill(0).map(() => new Array(2).fill(0));

// 初始化状态
dp[0] = [-prices[0], 0];

for (let i = 1; i < length; i++) {
// 当天持有股票
// 前一天持有,或前一天未持有,当天买入
dp[i][0] = Math.max(
dp[i - 1][0],
// 由于可以买卖多次,这里前一天未持有的收益是 dp[i-1][1]
dp[i-1][1] - prices[i]
);

// 当天未持有股票
// 前一天未持有,或前一天持有,当天卖出
dp[i][1] = Math.max(
dp[i - 1][1],
dp[i - 1][0] + prices[i]
);
}

return dp[length - 1][1];
}

本题也可以用贪心算法。
由于可以买卖多次,我们只需要贪心的按股票价格的涨买即可,即在股票价格低点买,涨了后卖。

1
2
3
4
5
6
7
8
9
10
11
12
function maxProfit(prices: number[]): number {
const length = prices.length;
if (length == 1) return 0;
let sum = 0;
for (let i = 1; i < length; i++) {
const diff = prices[i] - prices[i - 1];
if (diff > 0) {
sum += diff;
}
}
return sum;
};

买卖股票的最佳时机III(最多买卖两次)

3

本题又是一种变体。有原来的买卖不限次数变为限制买卖两次。

这样我们就不能再按上面的是否持有股票来定义状态了。

既然有限制买卖次数,那么我们就按买卖次数进行状态定义。

由于只能最多买卖两次,因此在每一天,我们有以下5种状态:

  • 未进行任何买卖操作
  • 只进行过一次买操作
  • 进行过一次买和一次卖操作,即完成一次交易
  • 完成一次交易后,又进行一次买操作
  • 完成两次交易

对于第一种状态,未进行任何操作,收益为0,不做记录。

我们定义buy1,buy2,sell1,sell2为 收益状态,分别表示:

  • buy1: 第一次买入后的 收益
  • sell1: 第一次卖出后的 收益
  • buy2: 第二次买入后的 收益
  • sell2: 第二次卖出后的 收益

这样,我们针对每次的买卖,只需要取最大值即可。
对于买入,收益为 减去 当前价格。对于卖出,收益为 加上 当前价格。

状态转移公式:
5

1
2
3
4
5
6
7
|--buy1 = max(buy1, -prices[i])
|
|--sell1 = max(sell1, buy1+priices[i])
|
|--buy2 = max(buy2, sell1-prices[i])
|
|--sell2 = max(sell2, buy2+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
28
function maxProfit3(prices: number[]): number { 
// 记录收益状态
// buy1: 完成第一次买入的收益状态,buy2: 完成第二次买入的收益状态
// 初始化时设置为负无穷,方便比较
let buy1 = Number.NEGATIVE_INFINITY, buy2 = Number.NEGATIVE_INFINITY;

// sell1: 完成第一次卖出时的收益状态, sell2:完成第二次卖出时的收益状态
// 初始化设置为0
let sell1 = 0, sell2 = 0;

for (const price of prices) {
// 由于buy1记录的是收益状态,因此这里price加负号,表示负收益
if (buy1 < -price) {
buy1 = -price;
}
if (sell1 < buy1 + price) {
sell1 = buy1 + price;
}
// 同理,第二次买入后的收益为第一次卖出的收益减去当前价格,取最大收益
if (buy2 < -price + sell1) {
buy2 = -price + sell1;
}
if (sell2 < buy2 + price) {
sell2 = buy2 + price;
}
}
return sell2;
}

买卖股票的最佳时机IV(最多买卖k次)

4

本题又是在最多买卖2次的基础上升级了,买卖次数限制为最多k次。

其思路也是一样,按照买卖次数进行状态定义。

我们定义 buys[i] 为第i次买入后的最大收益, sells[i] 为第i次卖出后的最大收益。

买入时,收益为上一次卖出后的收益减去当前价格。
卖出时,收益为本次买入后的收益加上当前价格。

那么,对应的状态转移方程是:

1
2
buys[i] = max(buys[i], sells[i-1]-price)    // 第i次买入后最大收益状态转移
sells[i] = max(sells[i], buys[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
function maxProfit(k: number, prices: number[]): number {

const length = prices.length;
if (length == 1) {
return 0;
}

// buys[i] 记录第i次买入时的收益状态,买入时收益是负的,这里都初始化为负无穷
let buys = new Array(k + 1).fill(Number.NEGATIVE_INFINITY);
// sells[i] 记录第i次卖出时的收益状态,卖出时收益是正的,这里初始化为0
let sells = new Array(k + 1).fill(0);

for (const price of prices) {
for (let i = 1; i <= k; i++) {
// 买入时,收益为完成上一次卖出时的收益减去当前价格
buys[i] = Math.max(buys[i], sells[i - 1] - price);
// 卖出时,收益为完成本次买入时的收益加上当前价格
sells[i] = Math.max(sells[i], buys[i] + price);
}
}

return sells[k];
};

本题的k如果设置为1,就是上面【买卖股票的最佳时机(只能买卖一次)】的解。
本题的k如果设置为2,就是上面【买卖股票的最佳时机III(最多买卖两次)】的解。

对于【买卖股票的最佳时机(只能买卖一次)】可以借鉴【买卖股票的最佳时机III(最多买卖两次)】,定义状态时不需要定义数组,因为只买卖一次,因此只需要定义一个买入和卖出两个常量状态即可。

【买卖股票的最佳时机(只能买卖一次)】使用买卖次数定义状态的代码:

1
2
3
4
5
6
7
8
9
10
11
12
function maxProfit(prices: number[]): number {
// 定义buy1为买入股票后的收益
let buy1 = Number.NEGATIVE_INFINITY;
// 定义sell1为卖出股票后的收益
let sell1 = 0;

for (const price of prices) {
buy1 = Math.max(buy1, 0-price);
sell1 = Math.max(sell1, buy1 + price);
}
return sell1;
}

买卖股票的最佳时机含手续费(买卖多次,每次有手续费)

5

本题是【买卖股票的最佳时机II(可以买卖多次)】的升级,可以买卖多次,但加了手续费,即每买卖一次需要交一次手续费。

状态定义和上面买卖股票II的一致。只不过,在每次卖出股票时,由于手续费的存在,在计算收益时需要减去手续费。

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
function maxProfit(prices: number[], fee: number): number {
const length = prices.length;
const dp = new Array(length).fill(0).map(() => new Array(2).fill(0));

// 初始化状态
dp[0] = [-prices[0], 0];

for (let i = 1; i < length; i++) {
// 当天持有股票
// 前一天持有,或前一天未持有,当天买入
dp[i][0] = Math.max(
dp[i - 1][0],
// 由于可以买卖多次,这里前一天未持有的收益是 dp[i-1][1]
dp[i-1][1] - prices[i]
);

// 当天未持有股票
// 前一天未持有,或前一天持有,当天卖出
dp[i][1] = Math.max(
dp[i - 1][1],
dp[i - 1][0] + prices[i] - fee // 卖出股票计算收益时,需要减去每笔的手续费
);
}

return dp[length - 1][1];
}

买卖股票的最佳时机含冷冻期(买卖多次,卖出有一天的冷冻期)

6

本题又是【买卖股票的最佳时机II(可以买卖多次)】的升级,在其基础上加入了冷冻期概念。

这样我们买卖股票II定义的状态中,未持有股票这种状态会分裂出两种状态:1. 未持有股票,且处于冷冻期内 2. 未持有股票,但未处于冷冻期内。

这样,我们总共就有了三种状态:

  1. 持有股票
  2. 未持有股票,且处于冷冻期内
  3. 未持有股票,但未处于冷冻期内

我们定义
dp[i][0] 表示第i天持有股票时的最大收益,
dp[i][1] 表示第i天手上不持有股票,且处于冷冻期内的最大收益,
dp[i][2] 表示第i天不持有股票,但未处于冷冻期内的最大收益。

相应的,状态转移公式也会发生变化。

  1. 持有股票时,可能是前一天就持有,然后持有到当天。也可能是前一天不持有,当天买入的股票,那么前一天必然不持有股票,也未在冷冻期内。
    dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i])
  2. 未持有股票,且处于冷冻期内。处于冷冻期内那么前一天必然持有股票且当天卖掉。此时的收益为前一天持有股票的最大收益加当天股票卖出的价格。
    dp[i][1] = dp[i-1][0] + prices[i]
  3. 未持有股票,但未处于冷冻期内。当天未处于冷冻期,前一天可能是处于冷冻期,也可能是未处于冷冻期。
    dp[i][2] = max(dp[i-1][1], dp[i-1][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
function maxProfit(prices: number[]): number {
const length = prices.length;
if (length == 1) return 0;

const dp = new Array(length).fill(0).map(() => new Array(3).fill(0));
// 第0天持有股票
dp[0][0] = -prices[0];

// 第0天未持有股票,因为第0天,不存在所谓的冷冻期,所以都初始化为0
// 因为上面在创建dp数组时已经默认填充0了,所以这里初始化为0可以不要
dp[0][1] = 0, dp[0][2] = 0;

for (let i = 1; i < length; i++) {
// 持有股票
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);

// 未持有股票,且处于冷冻期
dp[i][1] = dp[i - 1][0] + prices[i];

// 未持有股票,未处于冷冻期
dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
}

// 最后返回未持有股票的两种状态的最大值
return Math.max(dp[length-1][1], dp[length-1][2]);
};

总结

买卖股票这个系列的题,对条件不断的变种与延伸,可以说是动态规划算法很好的练习题目。
随着不断的升级与变种,加深对动态规划的理解,不同条件下如何定义状态,状态又是如何转移的,初始状态又该怎样定义等等。

即便是同一个题,在定义状态时也可以有不同的视角,可以说是非常不错的几个题目。