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

题目链接:

714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)icon-default.png?t=O83Ahttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

 


2.  算法原理

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

 

dp[i]表示:第i天结束之后,此时的最大利润 :两种情况:

 

                                1. f[i]表示:第i天结束之后,处于买入状态,此时的最大利润

  

                                2. g[i]表示:第i天结束之后,处于卖出状态,此时的最大利润

  

2. 状态转移方程

  

在第i-1天处于买入状态,看买入状态能不能到自己,看卖出状态能不能到买入状态,另一个状态也是如此,一共4种状态

   

买入状态到卖出状态到
买入状态什么都不干-prices[i](买股票)
卖出状态+prices[i](卖股票)-fee(手续费)什么都不干

1. f[i] = max(f[i-1],g[i-1]--prices[i])

  

2. g[i] = max(g[i-1],f[i-1]+prices[i]-fee)

  

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

  

f[0] = --prices[0]               g[0] = 0 

4. 填表顺序 

    

本题的填表顺序是:从左往右,两个表同时填

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

    

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

本题的返回值是:g[n-1]

 


3. 代码 

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

                                        2. 在填表之前初始化

                                        3. 填表(填表方法:状态转移方程)

                                        4. 确定返回值

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
    //1.  创建dp表
        vector<int>f(n);
        auto g=f;

    //2. 在填表之前初始化
        f[0]=-prices[0];

    //3. 填表(填表方法:状态转移方程)
    for(int i=1;i<n;i++)
    {
        f[i]=max(f[i-1],g[i-1]-prices[i]);
        g[i]=max(g[i-1],f[i-1]+prices[i]-fee);
    }

    //4. 确定返回值
    return g[n-1];

    }
};


未完待续~ 

Logo

助力广东及东莞地区开发者,代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展,成为松山湖开发者首选的工作与学习平台

更多推荐