织梦手机wap网站标签调用,什么是电子商务网站建设与管理,动漫制作技术升本可以升什么专业,苏州相城做网站的1、题目链接
leetcode 309. 买卖股票的最佳时机含冷冻期 2、题目分析
该题有我们可以定义三种状态#xff0c;买入状态#xff0c;可交易状态 #xff0c;冷冻期状态
我们可以建立一个n*3的二维数组来表示这三种状态#xff1a; 根据这个图可以看出#xff0c;
可以从…1、题目链接
leetcode 309. 买卖股票的最佳时机含冷冻期 2、题目分析
该题有我们可以定义三种状态买入状态可交易状态 冷冻期状态
我们可以建立一个n*3的二维数组来表示这三种状态 根据这个图可以看出
可以从买入状态卖出变成可交易状态或者从买入状态还是到买入状态(什么也不干),
可以从可交易状态到买入状态或者从可交易状态到可交易状态(什么也不干)
可以从冷冻期状态到可交易状态(只有这一种情况)
根据以上信息可以列出状态转移方程
dp[i][0]表示在第i天处于买入状态时所获得的最大利润
dp[i][1]表示在第i天处于可交易状态时所获得的最大利润
dp[i][2]表示在第i天处于冷冻期状态时所获得的最大利润
那么: dp[i][0]max(dp[i-1][0],dp[i-1][1]-prices[i]); dp[i][1]max(dp[i-1][1],dp[i-1][2]); dp[i][2]dp[i-1][0]prices[i]; 3、代码解析
int maxProfit(vectorint prices) {int nprices.size();vectorvectorintdp(n,vectorint(3));//dp[i][0]表示在第i天处于买入状态时所获得的最大利润//dp[i][1]表示在第i天处于可交易状态时所获得的最大利润//dp[i][2]表示在第i天处于冷冻期状态时所获得的最大利润//初始化dp[0][0]-prices[0];dp[0][1]0;dp[0][2]0;for(int i1;in;i){dp[i][0]max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]max(dp[i-1][1],dp[i-1][2]);dp[i][2]dp[i-1][0]prices[i];}return max(dp[n-1][1],dp[n-1][2]);}
完结
