【算法优选】 动态规划之简单多状态dp问题——贰

简介: 【算法优选】 动态规划之简单多状态dp问题——贰

🎋前言

动态规划相关题目都可以参考以下五个步骤进行解答:

  1. 状态表示
  2. 状态转移⽅程
  3. 初始化
  4. 填表顺序
  5. 返回值

后面题的解答思路也将按照这五个步骤进行讲解。

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

🚩题目描述

给定一个整数数组prices,其中第 prices[i] 表示第 i 天的股票价格

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

  • 示例 1:
    输入: prices = [1,2,3,0,2]
    输出: 3
    解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
  • 示例 2:
    输入: prices = [1]
    输出: 0
class Solution {
    public int maxProfit(int[] prices) {
    }
}

🚩算法思路:

🎈状态表示:

对于线性dp ,我们可以⽤「经验+题⽬要求」来定义状态表示:

  • 以某个位置为结尾…;
  • 以某个位置为起点…。

这里我们选择比较常⽤的⽅式,以某个位置为结尾,结合题目要求,定义⼀个状态表⽰:

由于有「买⼊」「可交易」「冷冻期」三个状态,因此我们可以选择⽤三个数组,其中:

  • dp[i][0] 表⽰:第 i 天结束后,处于「买⼊」状态,此时的最⼤利润;
  • dp[i][1]表⽰:第 i 天结束后,处于「可交易」状态,此时的最⼤利润;
  • dp[i][2] 表⽰:第 i 天结束后,处于「冷冻期」状态,此时的最⼤利润。

🎈状态转移方程

我们要谨记规则:

  1. 处于「买⼊」状态的时候,我们现在有股票,此时不能买股票,只能继续持有股票,或者卖出股票;
  2. 处于「卖出」状态的时候:
  • 如果「在冷冻期」,不能买⼊;
  • 如果「不在冷冻期」,才能买⼊。

对于 dp[i][0] ,我们有「两种情况」能到达这个状态:

  1. 在 i - 1 天持有股票,此时最⼤收益应该和 i - 1 天的保持⼀致: dp[i - 1][0] ;
  2. 在 i 天买⼊股票,那我们应该选择 i - 1 天不在冷冻期的时候买⼊,由于买⼊需要花钱,所以此时最⼤收益为: dp[i - 1][1] - prices[i]

两种情况应取最⼤值,因此: dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) 。

对于 dp[i][1] ,我们有「两种情况」能到达这个状态:

  1. 在 i - 1 天的时候,已经处于冷冻期,然后啥也不⼲到第 i 天,此时对应的状态为:dp[i - 1][2] ;
  2. 在 i - 1 天的时候,⼿上没有股票,也不在冷冻期,但是依旧啥也不干到第 i 天,此时对应的状态为 dp[i - 1][1] ;

两种情况应取最⼤值,因此: dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]) 。

对于 dp[1][i] ,我们只有「⼀种情况」能到达这个状态:

  1. 在 i - 1 天的时候,卖出股票。
  2. 因此对应的状态转移为: dp[i][2] = dp[i - 1][0] + prices[i]

🎈初始化:

三种状态都会用到前⼀个位置的值,因此需要初始化每⼀行的第⼀个位置:

  • dp[0][0] :此时要想处于「买⼊」状态,必须把第⼀天的股票买了,因此 dp[0][0] = -prices[0] ;
  • dp[0][1] :啥也不用干即可,因此 dp[0][1] = 0 ;
  • dp[0][2] :⼿上没有股票,买⼀下卖⼀下就处于冷冻期,此时收益为 0 ,因此 dp[0][2]= 0 。

🎈填表顺序:

根据「状态表示」,我们要三个表⼀起填,每⼀个表「从左往右」。

🎈返回值:

应该返回「卖出状态」下的最⼤值,因此应该返回 max(dp[n - 1][1], dp[n - 1][2])

🚩代码实现

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][3];
        dp[0][0] = - prices[0];
        for(int i = 1; i < n; i++) {
            dp[i][0] =  Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return Math.max(dp[n - 1][1], dp[n - 1][2]);
    }
}

🍃买卖股票的最佳时期含手续费(medium)

🚩题目描述

给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

  • 示例 1:
    输入:prices = [1, 3, 2, 8, 4, 9], fee = 2
    输出:8
    解释:能够达到的最大利润:
    在此处买入 prices[0] = 1
    在此处卖出 prices[3] = 8
    在此处买入 prices[4] = 4
    在此处卖出 prices[5] = 9
    总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
  • 示例 2:
    输入:prices = [1,3,7,5,10,3], fee = 3
    输出:6
class Solution {
    public int maxProfit(int[] prices, int fee) {
    }
}

🚩算法思路

🎈状态表示:

对于线性 dp ,我们可以⽤「经验 + 题⽬要求」来定义状态表⽰:

  1. 以某个位置为结尾,进行操作;
  2. 以某个位置为起点,进行操作。

这里我们选择比较常用的方式,以某个位置为结尾,结合题目要求,定义⼀个状态表示:

由于有「买⼊」「可交易」两个状态,因此我们可以选择用两个数组,其中:

  • f[i] 表示:第 i 天结束后,处于「买⼊」状态,此时的最大利润;
  • g[i] 表示:第 i 天结束后,处于「卖出」状态,此时的最大利润。

🎈状态转移方程:

我们选择在「卖出」的时候,支付这个手续费,那么在「买入」的时候,就不⽤再考虑⼿续费的问题。

对于 f[i] ,我们有两种情况能到达这个状态:

  1. 在 i - 1 天「持有」股票,第 i 天啥也不干。此时最⼤收益为 f[i - 1] ;
  2. 在 i - 1 天的时候「没有」股票,在第 i 天买⼊股票。此时最⼤收益为 g[i - 1] - prices[i])

两种情况下应该取最大值,因此 f[i] = max(f[i - 1], g[i - 1] -prices[i]) 。

对于 g[i] ,我们也有两种情况能够到达这个状态:

  1. 在 i - 1 天「持有」股票,但是在第 i 天将股票卖出。此时最大收益为: f[i - 1]+ prices[i] - fee) ,记得手续费;
  2. 在 i - 1 天「没有」股票,然后第 i 天啥也不干。此时最大收益为: g[i - 1] ;

两种情况下应该取最大值,因此 g[i] = max(g[i - 1], f[i - 1] + prices[i] - free) 。

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[] f = new int[prices.length];
        int[] g = new int[prices.length];
        f[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            f[i] = Math.max(f[i - 1],g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee); 
        }
        return g[prices.length - 1];
    }
}

🎈初始化:

由于需要用到前面的状态,因此需要初始化第⼀个位置。

  • 对于 f[0] ,此时处于「买入」状态,因此 f[0] = -prices[0] ;
  • 对于 g[0] ,此时处于「没有股票」状态,啥也不干即可获得最大收益,因此 g[0] = 0

🎈填表顺序:

毫⽆疑问是「从左往右」,但是两个表需要⼀起填。

🎈返回值:

应该返回「卖出」状态下,最后⼀天的最大值收益: g[n - 1]

🚩代码实现

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[] f = new int[prices.length];
        int[] g = new int[prices.length];
        f[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            f[i] = Math.max(f[i - 1],g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee); 
        }
        return g[prices.length - 1];
    }
}

🌳买卖股票的最佳时机 III

🚩题目描述

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

  • 示例 1:
    输入:prices = [3,3,5,0,0,3,1,4]
    输出:6
    解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
    随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
    -示例 2:
    输入:prices = [1,2,3,4,5]
    输出:4
    解释:在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
    因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
  • 示例 3:
    输入:prices = [7,6,4,3,1]
    输出:0
    解释:在这个情况下, 没有交易完成, 所以最大利润为 0。
  • 示例 4:
    输入:prices = [1]
    输出:0
class Solution {
    public int maxProfit(int[] prices) {
    }
}

🚩算法思路

🎈状态表示:

对于线性 dp ,我们可以⽤「经验 + 题目要求」来定义状态表示:

  1. 以某个位置为结尾,进行一系列操作;
  2. 以某个位置为起点,进行一系列操作。

这里我们选择比较常⽤的⽅式,以某个位置为结尾,结合题目要求,定义⼀个状态表⽰:

由于有「买⼊」「可交易」两个状态,因此我们可以选择用两个数组。但是这道题⾥⾯还有交易次数的限制,因此我们还需要再加上⼀维,用来表示交易次数。其中:

  • f[i][j] 表⽰:第 i 天结束后,完成了 j 次交易,处于「买⼊」状态,此时的最⼤利润;
  • g[i][j] 表⽰:第 i 天结束后,完成了 j 次交易,处于「卖出」状态,此时的最⼤利润。

🎈状态转移方程:

对于 f[i][j] ,我们有两种情况到这个状态:

  1. 在 i - 1 天的时候,交易了 j 次,处于「买⼊」状态,第 i 天啥也不干即可。此时最大利润为: f[i - 1][j] ;
  2. 在 i - 1 天的时候,交易了 j 次,处于「卖出」状态,第 i 天的时候把股票买了。此时的最⼤利润为: g[i - 1][j] - prices[i] 。

综上,我们要的是「最⼤利润」,因此是两者的最⼤值: f[i][j] = max(f[i - 1][j],g[i - 1][j] - prices[i]) 。

对于 g[i][j] ,我们也有两种情况可以到达这个状态:

  1. 在 i - 1 天的时候,交易了 j 次,处于「卖出」状态,第 i 天啥也不⼲即可。此时的最大利润为: g[i - 1][j] ;
  2. 在 i - 1 天的时候,交易了 j - 1 次,处于「买⼊」状态,第 i 天把股票卖了,然后就完成了 j ⽐交易。此时的最⼤利润为: f[i - 1][j - 1] + prices[i] 。但是这个状态不⼀定存在,要先判断⼀下。

综上,我们要的是最⼤利润,因此状态转移方程为:

g[i][j] = g[i - 1][j];
if(j >= 1) {
  g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}

🎈初始化:

由于需要用到 i = 0 时的状态,因此我们初始化第⼀行即可。

  • 当处于第 0 天的时候,只能处于「买⼊过⼀次」的状态,此时的收益为 -prices[0] ,因此 f[0][0] = - prices[0] 。
  • 为了取 max 的时候,⼀些不存在的状态「起不到干扰」的作用,我们统统将它们初始化为 - INF (用 INT_MIN 在计算过程中会有「溢出」的风险,这⾥ INF 折半取0x3f3f3f3f ,足够小即可)

🎈填表顺序:

从「上往下填」每⼀行,每⼀行「从左往右」,两个表「⼀起填」。

🎈返回值:

返回处于「卖出状态」的最⼤值,但是我们也「不知道是交易了⼏次」,因此返回 g 表最后⼀行的最大值。

🚩代码实现

class Solution {
    public int maxProfit(int[] prices) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int INF = 0x3f3f3f3f;
        int n = prices.length;
        int[][] f = new int[n][3];
        int[][] g = new int[n][3];
        for(int j = 0; j < 3; j++) {
            f[0][j] = g[0][j] = -INF;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for(int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                // 判断状态是否存在
                if (j - 1 >= 0) {
                    g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
                }
            }
        }
        //找出最后一行的最大值
        int ret = 0; 
        for(int j = 0; j < 3; j++) {
            ret = Math.max(ret, g[n - 1][j]);
        }
        return ret;
    }
}

⭕总结

关于《【算法优选】 动态规划之简单多状态dp问题——贰》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

相关文章
|
10天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
28 2
|
1月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
65 2
动态规划算法学习三:0-1背包问题
|
1月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
65 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
1月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
120 0
动态规划算法学习二:最长公共子序列
|
1月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
101 0
|
26天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
12天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
13天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。
|
12天前
|
机器学习/深度学习 算法 芯片
基于GSP工具箱的NILM算法matlab仿真
基于GSP工具箱的NILM算法Matlab仿真,利用图信号处理技术解析家庭或建筑内各电器的独立功耗。GSPBox通过图的节点、边和权重矩阵表示电气系统,实现对未知数据的有效分类。系统使用MATLAB2022a版本,通过滤波或分解技术从全局能耗信号中提取子设备的功耗信息。