多状态动态规划之买卖股票的最佳时机含手续费

简介: 多状态动态规划之买卖股票的最佳时机含手续费

1. 题目分析



题目链接选自力扣 : 买卖股票的最佳时机含手续费

2bc2c6d16b2358e9e656c39feea50f1b.png

根据示例 1 进行分析 :

4f0cb65ebadc98c9cc0d91d3e269a2b3.png


示例 2 :

image.png


总的来说, 和我们之前的 " 最佳买卖股票 " 有点类似. 遵循以下规则

  1. 当天手上没有股票可以选择不买入
  2. 当天手上有股票可以选择不卖出
  3. 当天手上没有股票可以选择买入
  1. 手上有股票必须卖出才可以进行买入操作
  2. 根据用户的不同操作, 尽可能的获得更多的利润. ( 低价收入高价卖出 )


PS : 这里的买入和卖出只得是一笔交易. 也就是说, 当你买入后再卖出时一瞬间会扣取手续费. 买入时并不会扣除, 只有卖掉股票时才会扣 !


2. 状态表示



以 i 为结尾, 表示从第一天到结束时, 所获得的最大利润

不难发现, 当第 i 天结束的时候, 又有两种情况.


  1. 第 i 天结束时为买入状态

这种情况, 我们以 f[i] 表示, 即从第一天开始到第 i 天结束时, 第 i 天处于买入状态时所获得的最大利润.


  1. 第 i 天结束时为卖出状态

这种情况, 我们以 g[i] 表示, 即从第一天开始到第 i 天结束时, 第 i 天处于卖出转态时所获得的最大利润.


3. 状态转移方程



根据上面两个状态表示可以看出, 这是一个多状态的问题. 因此我们对这两个状态分别进行状态转移方程的分析.

a379b71ba0bbcafac470cc768a856057.png

  1. 第 i 天结束时为买入状态

那么, 如何才能在第 i 天结束时为买入状态呢 ? 那我们就需要观察 i - 1 前一天的状态了.


  1. i - 1 为买入状态, 第 i 天不进行操作, 第 i 天结束后依然为买入状态

这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为买入状态时所获得的最大利润, 对应到状态表示中则为 f[i-1], 第 i 天由于不操作, 最终利润为 f[i-1]


  1. i - 1 为卖出状态, 第 i 天进行买入操作, 第 i 天结束后则为买入状态.


这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为卖出状态时所获得的最大利润, 对应到状态表示中则为 g[i-1], 并且在第 i 天买入, 最终利润为 g[i-1]-prices[i]


最终第 i 天结束时为买入状态的状态表示为 f[i] = Math.max(g[i-1]-prices[i], f[i-1]), 为两种情况下的最大利润.


  1. 第 i 天结束时为卖出状态
  1. i - 1 天为买入状态, 第 i 天进行卖出操作, 第 i 天结束后则为卖出状态


这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为卖出状态时所获得的最大利润, 对应到状态表示中则为 f[i-1], 由于在第 i 天进行卖出, 最终利润为 f[i-1] + prices[i]-fee


  1. i - 1 天为卖出状态, 第 i 天不进行操作, 则第 i 天接受后依然为卖出状态 ( 可交易 )


这种情况下, 其对应的花费为从第一天到第 i - 1 天结束为卖出状态时所获得的最大利润, 对应到状态表示中则为 g[i-1], 由于第 i 天不进行操作. 因此最终利润为 g[i-1]


最终第 i 天结束时为卖出状态的状态表示为 g[i] = Math.max(f[i-1] + prices[i]-fee, g[i-1]), 为两种情况下的最大利润


4. 初始化



根据状态转移方程, f[0] 和 g[0] 在填表时会发生越界错误, 因此需要单独进行初始化.

如果第 1 天结束时为买入状态, 之后整个股票交易就结束了, 此时还没有卖出股票, 手上的利润为 -prices[0] ( 负数 )


如果第 1 天结束时为卖出状态, 之后整个股票交易就结束了, 此时为 0 , 等同于这一天买入后又卖出去了. ( 这句话需要各位好好体会一下 )


5. 填表顺序



根据状态转移方程, 想要知道 i 位置结束时获得的最大利润, 要先知道前一天的最大利润. 因此填表顺序为从左往右


6. 返回值



返回第 n 天结束时, 所获得的最大利润. 对应到我们的状态表示中则为两种不同状态下第 n 天的最大值. 即 Math.max(f[n-1], g[n-1]) ( 注意 n 为数组长度, 和下标的对应关系 )


7. 代码演示



class Solution {
    public int maxProfit(int[] prices, int fee) {
        // 1. 创建 dp 表
        int n = prices.length;
        int[] f = new int[n]; // i 位置结束时为买入状态所获得的最大利润
        int[] g = new int[n]; // i 位置结束时为卖出状态所获得的最大利润
        // 2. 初始化
        f[0] = -prices[0];
        // 3. 填写 dp 表
        for(int i = 1; i < n; i++) {
             f[i] = Math.max(g[i - 1]-prices[i], f[i - 1]);
             g[i] = Math.max(f[i - 1] + prices[i]-fee, g[i - 1]);
        }
        // 4. 确认返回值
        return Math.max(f[n - 1], g[n - 1]);
    }
}


相关文章
|
7月前
【动态规划】买卖股票问题
【动态规划】买卖股票问题
92 0
|
算法
【动态规划刷题 7】 买卖股票的最佳时机含冷冻期&& 买卖股票的最佳时机含手续费
【动态规划刷题 7】 买卖股票的最佳时机含冷冻期&& 买卖股票的最佳时机含手续费
|
算法
【动态规划刷题 8】买卖股票的最佳时机 III && 买卖股票的最佳时机 IV
【动态规划刷题 8】买卖股票的最佳时机 III && 买卖股票的最佳时机 IV
|
7月前
leetcode-714:买卖股票的最佳时机含手续费
leetcode-714:买卖股票的最佳时机含手续费
42 0
|
6月前
动态规划——买卖股票的最佳时机含冷冻期
动态规划——买卖股票的最佳时机含冷冻期
38 1
|
7月前
|
算法
【力扣】121. 买卖股票的最佳时机、122.买卖股票的最佳时机Ⅱ
【力扣】121. 买卖股票的最佳时机、122.买卖股票的最佳时机Ⅱ
|
7月前
代码随想录 Day43 动态规划11 LeetCode T309 买卖股票的最佳时期含冷冻期 T714买卖股票的最佳时机含手续费
代码随想录 Day43 动态规划11 LeetCode T309 买卖股票的最佳时期含冷冻期 T714买卖股票的最佳时机含手续费
51 0
|
算法
代码随想录算法训练营第五十天 | LeetCode 309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费、股票系列总结
代码随想录算法训练营第五十天 | LeetCode 309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费、股票系列总结
79 1
|
算法
【学会动态规划】买卖股票的最佳时机含手续费(16)
【学会动态规划】买卖股票的最佳时机含手续费(16)
33 0
|
算法
【学会动态规划】买卖股票的最佳时机 III(17)
【学会动态规划】买卖股票的最佳时机 III(17)
33 0