【学会动态规划】买卖股票的最佳时机含手续费（16）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】买卖股票的最佳时机含手续费（16）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

【学会动态规划】买卖股票的最佳时机含手续费（16）,学会动态规划,动态规划,算法

这道题也不难理解，主要有两个点需要注意，

首先是买了股票需要卖了才能再买（手里一次只能有一个股票）

买卖一次股票需要付一次手续费。

2. 算法原理

1. 状态表示

dp[ i ] 表示的是第 i 天结束之后，所能获得的最大利润，

实际上，这个也能细分成两种情况：

一种是第 i 天购买了股票，我们设为 f [ i ]

一种是第 i 天啥也不干，我们设为 g [ i ]

2. 状态转移方程

我们通过最近的一步来推导状态转移方程，总共需要分析两个：

如果第 i 天要进入买入股票的状态，那如果前一天已经买了，就什么都不用干，

如果第 i 天要进入买入股票的状态，如果前一天没买，那今天买就行，

所以 f [ i ] = max( f [ i - 1 ]，g [ i - 1 ] - p [ i ] )

如果第 i 要进入卖出股票的状态，如果前一天没买，就啥都不用干，

如果第 i 要进入卖出股票的状态，如果前一天买了，那今天卖掉就行，

所以 g [ i ] = max( g [ i - 1 ]，f [ i - 1 ] + p[ i ] - fee )

记得要减手续费 fee。

3. 初始化

f [ 0 ] = -p [ 0 ]（就是买了当天的股票）g [ 0 ] = 0（啥都不干）

4. 填表顺序

从左往右，两个表同时填即可。

5. 返回值

g [ n - 1 ]

3. 代码编写

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<int> f(n);
        auto g = f;
        f[0] = -prices[0];
        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);
        }
        return g[n - 1];
    }
};