模版题-动态规划-买卖股票的最佳时机II ( I和II递推公式对比 )
- 版权声明：本站原创文章，于2026-05-22，由 管理员 发表。
- 转载请注明： 模版题-动态规划-买卖股票的最佳时机II ( I和II递推公式对比 ) | CodeGarden
**买卖股票的最佳时机I中，由于只允许买卖股票一次，所以收益不可以复用。**
体现在递推公式上：
```
for i in range( 1, n ):
dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ], dp[ i - 1 ][ 1 ] + prices[ i ] )
dp[ i ][ 1 ] = max( dp[ i - 1 ][ 1 ], -prices[ i ] )
```
**买卖股票的最佳时机II中，允许多次买卖股票，只需保证同一时间只持有一只股票即可，所以买卖股票的收益可以复用。**
体现在递推公式上：
```
for i in range( 1, n ):
dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ], dp[ i - 1 ][ 1 ] + prices[ i ] )
dp[ i ][ 1 ] = max( dp[ i - 1 ][ 1 ], dp[ i - 1 ][ 0 ] - prices[ i ] )
```
```python
class Solution:
# 一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
# 在每一天，可以决定是否购买和/或出售股票。
# 你在任何时候最多只能持有一股股票。
# 然而，可以在同一天多次买卖该股票，但要确保你持有的股票不超过一股。
# 返回能获得的最大利润。
def maxProfit(self, prices: List[int]) -> int:
# dp[ i ][ 0 ]表示在第i天没有股票的最高金额
# dp[ i ][ 1 ]表示在第i天持有股票的最高金额
n = len( prices )
dp = [ [ 0, 0 ] for _ in range( n ) ]
dp[ 0 ][ 0 ] = 0
dp[ 0 ][ 1 ] = -prices[ 0 ]
for i in range( 1, n ):
dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ], dp[ i - 1 ][ 1 ] + prices[ i ] )
dp[ i ][ 1 ] = max( dp[ i - 1 ][ 1 ], dp[ i - 1 ][ 0 ] - prices[ i ] )
return dp[ n - 1 ][ 0 ]
```