可以免费网络推广网站,wordpress看文,商标注册类别45类明细,深圳自适应网站制作目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析
题目链接188. 买卖股票的最佳时机 IV - 力扣LeetCode 这道题跟上一道题是一模一样啊我的评价是当一个 CV 工程师
我马上 CV 出结果
上一题的代码 这一题的代码 虽然话是这么说我们还是再做一遍这道题
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. 代码编写
class Solution {
public:int maxProfit(int k, vectorint prices) {int n prices.size();vectorvectorint f(n, vectorint(k 1, -0x3f3f3f3f));auto g f;f[0][0] -prices[0], g[0][0] 0;for(int i 1; i n; i) {for(int j 0; j k 1; j) {f[i][j] max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] g[i - 1][j];if(j 0) g[i][j] max(g[i][j], f[i - 1][j - 1] prices[i]);}}int ans 0;for(auto e : g[n - 1]) ans max(ans, e);return ans;}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
