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

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

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


相关文章
|
架构师 测试技术 uml
这才是业务用例,别再搞错了!
这才是业务用例,别再搞错了!
1515 0
|
存储 移动开发 JavaScript
session、cookie、localStorage和SessionStorage怎么使用,区别和特点
session、cookie、localStorage和SessionStorage怎么使用,区别和特点
124 0
|
C++
C++绑定器和函数对象
band1st和band2nd本身还是一个函数对象。
162 0
|
前端开发 算法 JavaScript
牛客面经每日一总结(四)
牛客面经每日一总结(四)
LeetCode 15 三数之和
LeetCode 15 三数之和
128 0
|
算法 测试技术
Leetcode投资的最大收益(动态规划/贪心算法)
Leetcode投资的最大收益(动态规划/贪心算法)
|
JSON API 开发工具
API参考—实例管理—CreateDBInstance
API参考—实例管理—CreateDBInstance
剑指offer之左旋转字符串
剑指offer之左旋转字符串
128 0