学会动态规划买卖股票的最佳时机 III17

目录

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

---

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

买卖股票的题目大体都是一样的，不一样的地方就是他们在细节方面的一些差别，

比如这道题，他限制最多可以完成两笔交易。（手里只能有一个股票）

2. 算法原理

1. 状态表示

dp[ i ] 表示到第 i 天的时候，所能获得的最大利润，

实际上，我们还是可以将他分成两种情况：

买入状态和可交易状态，而且我们需要记录完成了几次交易

f [ i ][ j ] 表示第 i 天结束之后，完成了 j 次交易，处于 “买入” 状态的最大利润，

g [ i ][ j ] 表示第 i 天结束之后，完成了 j 次交易，处于 “可交易” 状态的最大利润，

这里再次说明，买入状态指的是手里有股票，

而可交易状态表示的是手里没有股票。

2. 状态转移方程

我们先从 f [ i ][ j ] 开始分析，就两种情况，一种是昨天是买入，一种是昨天是可交易状态，

买入状态啥也不干就行，可交易状态只要在今天买入就能进入买入状态，所以：

f [ i ][ j ] = max( f [ i - 1 ][ j ]，g [ i - 1 ][ j ] - p [ i ] )

然后是 g [ i ][ j ] ，也是同样的两种情况，

如果是买入状态就卖出，当天的 j 是比现在小1的，如果是可交易状态，就啥也不干就行，所以：

g [ i ][ j ] = max( g[ i - 1 ][ j ]，f [ i - 1 ][ j - 1 ] p [ i ] )

3. 初始化

为了防止越界，我们需要对他进行一些特殊的处理，

然后为了防止前面的值影响后面的值，我们需要把数组内容初始化成负无穷大

然后把 f [ 0 ][ 0 ] = -p[ 0 ]，让 g [ 0 ][ 0 ] = 0 即可

4. 填表顺序

从上往下，从左往右，两个表一起填

5. 返回值

g 表最后一行的最大值

3. 代码编写

1.  
   class Solution {
2.  
   public:
3.  
   int maxProfit(vector<int>& prices) {
4.  
   int n = prices.size();
5.  
   vector<vector<int>> f(n, vector<int>(3, -0x3f3f3f3f));
6.  
   auto g = f;
7.  
   f[0][0] = -prices[0], g[0][0] = 0;
8.  
   for(int i = 1; i < n; i ) {
9.  
   for(int j = 0; j < 3; j ) {
10.  
    f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
11.  
    g[i][j] = g[i - 1][j];
12.  
    if(j > 0) g[i][j] = max(g[i][j], f[i - 1][j - 1] prices[i]);
13.  
    }
14.  
    }
15.  
    int ans = 0;
16.  
    for(auto e : g[n - 1]) ans = max(ans, e);
17.  
    return ans;
18.  
    }
19.  
    };

写在最后：

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~

这篇好文章是转载于：学新通技术网