网站维护升级,装修设计师培训班,怎么查楼盘预售许可证,餐饮小程序开发1. 买卖股票的最佳时机III 题目链接#xff1a; 123. 买卖股票的最佳时机 III - 力扣#xff08;LeetCode#xff09;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 2. 题目解析 3. 算法原理 状态表示#xff1a;以某一个位置为结尾或者…1. 买卖股票的最佳时机III 题目链接 123. 买卖股票的最佳时机 III - 力扣LeetCodehttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/ 2. 题目解析 3. 算法原理 状态表示以某一个位置为结尾或者以某一个位置为起点 dp[i]表示第i天结束之后此时的最大利润 两种情况 1. f[i][j]表示第i天结束之后完成了j次交易处于买入状态此时的最大利润 2. g[i][j]表示第i天结束之后完成了j次交易处于卖出状态此时的最大利润 2. 状态转移方程 在第i-1天处于买入状态看买入状态能不能到自己看卖出状态能不能到买入状态另一个状态也是如此一共4种状态 买入状态到卖出状态到买入状态什么都不干-prices[i](买股票)卖出状态prices[i](交易次数1)什么都不干 1. f[i][j] max(f[i-1][j] , g[i-1][j] - prices[i]) 2. g[i][j] max(g[i-1][j] , f[i-1][j-1] prices[i] 3. 初始化 把dp表填满不越界让后面的填表可以顺利进行 因为是在第i-1天处于买入/卖出状态所以当交易次数为0时就相当于在第i天为-1那么就会导致越界 所以我们可以修改一下第二个状态转移方程来判断一下我们可以看到卖出状态到自己的情况是不会改变的所以只用修改买入状态到卖出状态 1. g[i][j] g[i-1][j]此状态一定不会越界 2. if(j-10) g[i][j] max(g[i][j] , f[i-1][j-1] prices[i] 在查找f[i-1][j-1] prices[i]状态的时候先判断一下 下标是否合法(if(j-10))然后再求max 定义一个正无穷大/小的时候涉及到需要进行加减操作的时候不要使用INT_MIN/MAX因为如果INT_MIN减去一个数的话就会变成一个非常大的整数而导致溢出所以我们最好用 /- 0x3f3f3f3f 来表示最小值 本题初始化就是先将表里的所有值都初始化为-无穷大再把f[0][0] --prices[0],g[0][0] 0 4. 填表顺序 本题的填表顺序是从上往下填写每一行每一行从左往右两个表同时填 5. 返回值 题目要求 状态表示 因为是要最大利润所以买入状态不用考虑 本题的返回值是g表里最后一行里面的最大值 4. 代码 动态规划的固定四步骤1. 创建一个dp表 2. 在填表之前初始化 3. 填表填表方法状态转移方程 4. 确定返回值 class Solution {
public:const int INF0x3f3f3f3f;//将无穷大赋予给INFint maxProfit(vectorint prices) {int n prices.size();//1. 创建dp表//3交易次数的三列012,再将所有的位置都变成负无穷大vectorvectorintf(n,vectorint(3,-INF));auto gf;//2. 在填表之前初始化f[0][0]-prices[0];g[0][0]0;//3. 填表填表方法状态转移方程for(int i1;in;i){for(int j0;j3;j)//j只有012三种状态{f[i][j]max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]g[i-1][j];if(j1)g[i][j]max(g[i][j],f[i-1][j-1]prices[i]);}}//g表里最后一行里面的最大值int ret0;for(int j0;j3;j)retmax(ret,g[n-1][j]);return ret;}
}; 未完待续~
