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]); }
