动态规划——买卖股票的最佳时机含冷冻期

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(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(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 i=1;i<n;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]);}

完结！