虚拟主机怎么弄网站,新品网络推广,设计师的灵感来源,wordpress文章列表分页代码动态规划解题步骤#xff1a;
1.确定状态表示#xff1a;dp[i]是什么
2.确定状态转移方程#xff1a;dp[i]等于什么
3.初始化#xff1a;确保状态转移方程不越界
4.确定填表顺序#xff1a;根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接#xff1a;188.…动态规划解题步骤
1.确定状态表示dp[i]是什么
2.确定状态转移方程dp[i]等于什么
3.初始化确保状态转移方程不越界
4.确定填表顺序根据状态转移方程即可确定填表顺序
5.确定返回值
题目链接188. 买卖股票的最佳时机 IV - 力扣LeetCode 题解
本题与动态规划17123. 买卖股票的最佳时机 III 几乎无异
1.状态表示
f[k][i]表示截止第i天第i天为可买入状态的最大利润且当前已交易k次
g[k][i]表示截止第i天第i天为可卖出状态的最大利润且当前已交易k次
2.状态转移方程
f[k][i]max(f[k][i-1],g[k-1][i-1]prices[i])
g[k][i]max(g[k][i-1],f[k][i-1]-prices[i])
3.初始化初始化第一列为负无穷-0x3f3f3f3f另外 f[0][0]0 g[0][0]-prices[0];
注意对于f表其本应该初始化第一行和第一列但是为了优化代码和g表保持一致可以只初始化第一列对于第一行的数据只需对其状态转移方程添加位置判断即可对于不合法的位置其状态转移方程为f[k][i-1]合法位置的状态转移方程为max(f[k][i-1],g[k-1][i-1]prices[i])
4.填表顺序从上往下从左往右两个表一起填
5.返回值返回第n-1天为可买入状态的最大利润交易次数可能为0、1、2......K所以需要遍历第n-1列
class Solution {
public:int maxProfit(int K, vectorint prices) {const int INF0x3f3f3f3f;//f[k][i]表示截止第i天第i天为可买入状态的最大利润且当前已交易k次//g[k][i]表示截止第i天第i天为可卖出状态的最大利润且当前已交易k次//第i天为可买入状态则前一天有两种情况前一天为可买入状态交易次数相同今天什么也没做// 前一天为可卖出状态交易次数少1今天卖出了股票//f[k][i]max(f[k][i-1],g[k-1][i-1]prices[i])//第i天为可卖出状态则前一天有两种情况前一天为可卖出状态交易次数相同今天什么也没做// 前一天为可买入状态交易次数相同今天买了股票//g[k][i]max(g[k][i-1],f[k][i-1]-prices[i])size_t nprices.size();//处理边界条件if(n1) return 0;//创建dp表vectorvectorint f(K1,vectorint(n,-INF));vectorvectorint g(K1,vectorint(n,-INF));//初始化创建dp表时已初始化一部分相当于初始化了第一列f[0][0]0;g[0][0]-prices[0];//填表for(int k0;kK;k){for(int i1;in;i){if(k-10) f[k][i]max(f[k][i-1],g[k-1][i-1]prices[i]);else f[k][i]f[k][i-1];g[k][i]max(g[k][i-1],f[k][i-1]-prices[i]);}}//返回值int ansINT_MIN;for(int k0;kK;k)if(f[k][n-1]ans) ansf[k][n-1];return ans;}
};
