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

25-02-21 21:00

4283

11027

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="htmledit_views">

1. 买卖股票的最佳时机含冷冻期

题目链接：

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

2. 题目解析

3. 算法原理

状态表示：以某一个位置为结尾或者以某一个位置为起点

dp[i][0]表示：第i天结束之后，处于买入状态，此时的最大利润

dp[i][1]表示：第i天结束之后，处于可交易状态，此时的最大利润

dp[i][2]表示：第i天结束之后，处于冷冻期状态，此时的最大利润

2. 状态转移方程

在第i-1天处于买入状态，看买入状态能不能到自己，看可交易状态能不能到买入状态，看冷冻期状态能不能到买入状态，其他两个状态也是如此，一共9种状态

class="table-box">
买入状态到 可交易状态到 冷冻期状态到

买入状态

0
什么都不干（yes） -prices[i](买股票) 不能
可交易状态1 不能 什么都不干（yes） 什么都不干（yes）
冷冻期状态2 +prices[i](卖股票) 不能不能

根据最近的一步来划分问题：

1. dp[i][0]=max(dp[i-1][0] , dp[i-1][1] - prices[i])

2. dp[i][1]=max(dp[i-1][1] , dp[i-1][2])

3. dp[i][2]=dp[i-1][0]+prices[i]

3. 初始化 ：把dp表填满不越界，让后面的填表可以顺利进行

要想处于买入状态就需要进行买入： dp[0][0]=-prices[0]

dp[0][1]=0 dp[0][2]=0

4. 填表顺序

本题的填表顺序是：从左往右，三个表同时填（因为填写其中一个表需要用到其他两个表）

5. 返回值：题目要求 + 状态表示



因为是要最大利润，所以买入状态不用考虑

本题的返回值是：max(dp[n-1][1],dp[n-1][2])

4. 代码

动态规划的固定四步骤：1. 创建一个dp表

2. 在填表之前初始化

3. 填表（填表方法：状态转移方程）

4. 确定返回值

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">

class="hljs-ln-code"> class="hljs-ln-line">class Solution {

class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2">

 class="hljs-ln-code"> class="hljs-ln-line">public: class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    int maxProfit(vector<int>& prices) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line"> 
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">    int n = prices.size();
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">    //1.  创建一个规模(n*3)的dp表
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">    vector<vector<int>>dp(n, vector(3));
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">        //2. 在填表之前初始化
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">        dp[0][0]=-prices[0];
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line"> 
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">         //3. 填表（填表方法：状态转移方程）
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">    for(int i=1;i<n;i++)
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">    {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">        dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line">        dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">        dp[i][2]=dp[i-1][0]+prices[i];
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line"> 
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line">        //4. 确定返回值
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line">        return max(dp[n-1][1],dp[n-1][2]);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line">};

class="hide-preCode-box">

class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

未完待续~

data-report-view="{"mod":"1585297308_001","spm":"1001.2101.3001.6548","dest":"https://blog.csdn.net/hedhjd/article/details/143648924","extend1":"pc","ab":"new"}">>

注：本文转载自blog.csdn.net的迷迭所归处的文章"https://blog.csdn.net/hedhjd/article/details/143648924"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！