Day45 | 动态规划 ：状态机DP 买卖股票的最佳时机含冷冻期&&买卖股票的最佳时机含手续费

动态规划应该如何学习？-CSDN博客

本次题解参考自灵神的做法，大家也多多支持灵神的题解

买卖股票的最佳时机【基础算法精讲 21】_哔哩哔哩_bilibili

希望读者在阅读之前先看完这篇博客

Day43 | 动态规划 ：状态机DP 买卖股票的最佳时机&&买卖股票的最佳时机II-CSDN博客

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

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

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

这题笔者还不够理解，后续再刷的时候再次回顾

思路：

在 122. 买卖股票的最佳时机 II 的基础上，只需修改一处：在计算持有股票的状态时，把 dfs(i−1,0) 改成 dfs(i−2,0)。道理和 198. 打家劫舍 是一样的，因为第 i 天买股票的话第 i−1 天不能卖，只能从第 i−2 天没有股票的状态转移过来。注意 dfs(i−2,0) 并不意味着第 i−2 天一定卖了股票，而是在没有股票下的最优状态。

请注意，这会导致边界条件多了一个 dfs(−2,0)=0

请注意，dfs(−2,1) 是访问不到的，所以下面翻译成递推时，无需初始化这个状态（不需要写 f[0][1]=−∞）。

1.回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(int i,int status,vector<int>& prices)
    {
        if(i<0)
            if(status==1)
                return INT_MIN;
            else
                return 0;
        if(status==1)
            return max(dfs(i-1,1,prices),dfs(i-2,0,prices)-prices[i]);
        else
            return max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);
    }
    int maxProfit(vector<int>& prices) {
        return dfs(prices.size()-1,0,prices);
    }
};

2.记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int dfs(int i,int status,vector<int>& prices,vector<vector<int>>& dp)
    {
        if(i<0)
            if(status==1)
                return INT_MIN;
            else
                return 0;
        if(dp[i][status]!=-1)
            return dp[i][status];
        if(status==1)
            return dp[i][status]=max(dfs(i-1,1,prices,dp),dfs(i-2,0,prices,dp)-prices[i]);
        else
            return dp[i][status]=max(dfs(i-1,0,prices,dp),dfs(i-1,1,prices,dp)+prices[i]);
    }
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size(),vector<int>(2,-1));
        return dfs(prices.size()-1,0,prices,dp);
    }
};


3.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size()+2,vector<int>(2,0));
        dp[0][1]=INT_MIN/2;
        dp[1][1]=INT_MIN/2;
        for(int i=0;i<prices.size();i++)
        {
            dp[i+2][1]=max(dp[i+1][1],dp[i][0]-prices[i]);
            dp[i+2][0]=max(dp[i+1][0],dp[i+1][1]+prices[i]);
        }
        return dp[prices.size()+1][0];
    }
};

714.买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

思路：

就是每次卖了股票以后减个手续费就完事

在买卖股票II里面的+prices[i]后面减去fee即可，每次卖完股票赚的利润就是原来的利润减去手续费

1.回溯法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int dfs(int i,int status,vector<int>& prices,int fee)
    {
        if(i<0)
            if(status==1)
                return INT_MIN/2;
            else
                return 0;
        if(status==1)
            return max(dfs(i-1,1,prices,fee),dfs(i-1,0,prices,fee)-prices[i]);
        else
            return max(dfs(i-1,0,prices,fee),dfs(i-1,1,prices,fee)+prices[i]-fee);
    }
    int maxProfit(vector<int>& prices, int fee) {
        return dfs(prices.size()-1,0,prices,fee);
    }
};

2.记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int dfs(int i,int status,vector<int>& prices,int fee,vector<vector<int>>& dp)
    {
        if(i<0)
            if(status==1)
                return INT_MIN/2;
            else
                return 0;
        if(dp[i][status]!=-1)
            return dp[i][status];
        if(status==1)
            return dp[i][status]=max(dfs(i-1,1,prices,fee,dp),dfs(i-1,0,prices,fee,dp)-prices[i]);
        else
            return dp[i][status]=max(dfs(i-1,0,prices,fee,dp),dfs(i-1,1,prices,fee,dp)+prices[i]-fee);
    }
    int maxProfit(vector<int>& prices,int fee) {
        vector<vector<int>> dp(prices.size(),vector<int>(2,-1));
        return dfs(prices.size()-1,0,prices,fee,dp);
    }
};

3.动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices,int fee) {
        vector<vector<int>> dp(prices.size()+1,vector<int>(2,0));
        dp[0][0]=0;
        dp[0][1]=INT_MIN/2;
        for(int i=0;i<prices.size();i++)
        {
            dp[i+1][1]=max(dp[i][1],dp[i][0]-prices[i]);
            dp[i+1][0]=max(dp[i][0],dp[i][1]+prices[i]-fee);
        }
        return dp[prices.size()][0];
    }
};