成都做网站设计公司价格,12306网站谁建设的,室内设计软件下载网站大全,建设银行网站需要什么浏览器目录
动态规划怎么学#xff1f;
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后#xff1a; 动态规划怎么学#xff1f;
学习一个算法没有捷径#xff0c;更何况是学习动态规划#xff0c;
跟我…目录
动态规划怎么学
1. 题目解析
2. 算法原理
1. 状态表示
2. 状态转移方程
3. 初始化
4. 填表顺序
5. 返回值
3. 代码编写
写在最后 动态规划怎么学
学习一个算法没有捷径更何况是学习动态规划
跟我一起刷动态规划算法题一起学会动态规划
1. 题目解析 这道题也不难理解主要有两个点需要注意
首先是买了股票需要卖了才能再买手里一次只能有一个股票
买卖一次股票需要付一次手续费。
2. 算法原理
1. 状态表示
dp[ i ] 表示的是第 i 天结束之后所能获得的最大利润
实际上这个也能细分成两种情况
一种是第 i 天购买了股票我们设为 f [ i ]
一种是第 i 天啥也不干我们设为 g [ i ]
2. 状态转移方程
我们通过最近的一步来推导状态转移方程总共需要分析两个
如果第 i 天要进入买入股票的状态那如果前一天已经买了就什么都不用干
如果第 i 天要进入买入股票的状态如果前一天没买那今天买就行
所以 f [ i ] max( f [ i - 1 ]g [ i - 1 ] - p [ i ] )
如果第 i 要进入卖出股票的状态如果前一天没买就啥都不用干
如果第 i 要进入卖出股票的状态如果前一天买了那今天卖掉就行
所以 g [ i ] max( g [ i - 1 ]f [ i - 1 ] p[ i ] - fee )
记得要减手续费 fee。
3. 初始化
f [ 0 ] -p [ 0 ]就是买了当天的股票g [ 0 ] 0啥都不干
4. 填表顺序
从左往右两个表同时填即可。
5. 返回值
g [ n - 1 ]
3. 代码编写
class Solution {
public:int maxProfit(vectorint prices, int fee) {int n prices.size();vectorint f(n);auto g f;f[0] -prices[0];for(int i 1; i n; i) {f[i] max(f[i - 1], g[i - 1] - prices[i]);g[i] max(g[i - 1], f[i - 1] prices[i] - fee);}return g[n - 1];}
};
写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果感到有所收获的话可以给博主点一个赞哦。
如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~
