【算法优选】 动态规划之路径问题——贰

简介: 【算法优选】 动态规划之路径问题——贰


🎋前言

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

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

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

🌲下降最小路径和

🚩题目描述

给你一个 n x n 的 方形 整数数组 matrix ,请你找出并返回通过 matrix 的下降路径 的 最小和 。

下降路径 可以从第一行中的任何元素开始,并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列(即位于正下方或者沿对角线向左或者向右的第一个元素)。具体来说,位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

  • 示例 1:

输入:matrix = [[2,1,3],[6,5,4],[7,8,9]]

输出:13

解释:如图所示,为和最小的两条下降路径

  • 示例 2:

输入:matrix = [[-19,57],[-40,-5]]

输出:-59

解释:如图所示,为和最小的下降路径

class Solution {
    public int minFallingPathSum(int[][] matrix) {
    }
}

🚩算法思路:

关于这⼀类题,由于我们做过类似的,因此「状态表⽰」以及「状态转移」是⽐较容易分析出来的。

⽐较难的地⽅可能就是对于「边界条件」的处理。

  1. 状态表⽰:对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
  • 从 [i, j] 位置出发,到达⽬标位置有多少种⽅式;
  • 从起始位置出发,到达 [i, j] 位置,⼀共有多少种⽅式

这⾥选择第⼆种定义状态表⽰的⽅式:

dp[i][j] 表⽰:到达 [i, j] 位置时,所有下降路径中的最⼩和。

  1. 状态转移⽅程:对于普遍位置 [i, j] ,根据题意得,到达 [i, j] 位置可能有三种情况:
  • 从正上⽅ [i - 1, j] 位置转移到 [i, j] 位置;
  • 从左上⽅ [i - 1, j - 1] 位置转移到 [i, j] 位置;
  • 从右上⽅ [i - 1, j + 1] 位置转移到 [i, j] 位置;

我们要的是三种情况下的「最⼩值」,然后再加上矩阵在 [i, j] 位置的值。于是 dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1][j +1])) + matrix[i][j] 。

  1. 初始化:可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
  • 辅助结点⾥⾯的值要「保证后续填表是正确的」;
  • 「下标的映射关系」。

在本题中,需要「加上⼀⾏」,并且「加上两列」。所有的位置都初始化为⽆穷⼤,然后将第⼀⾏初始化为0 即可。

  1. 填表顺序:
    根据「状态表⽰」,填表的顺序是「从上往下」。
  2. 返回值:
    注意这⾥不是返回 dp[m][n] 的值!

题⽬要求「只要到达最后⼀⾏」就⾏了,因此这⾥应该返回「dp表中最后⼀⾏的最⼩值」。

🚩代码实现

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];
        for(int i = 1; i <= n; i++) {
            dp[i][0] = dp[i][n + 1] = Integer.MAX_VALUE;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1],dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
    
        int ret = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++) {
            ret = Math.min(ret, dp[n][j]);
        }
        return ret;
    }
}

🎍最小路径和

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

  • 示例 1:

    输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
    输出:7
    解释:因为路径 1→3→1→1→1 的总和最小。
  • 示例 2:
    输入:grid = [[1,2,3],[4,5,6]]
    输出:12
class Solution {
    public int minPathSum(int[][] grid) {
    }
}

🚩算法思路

像这种表格形式的动态规划,是⾮常容易得到「状态表⽰」以及「状态转移⽅程」的,可以归结到「不同路径」⼀类的题⾥⾯。

  1. 状态表⽰:对于这种路径类的问题,我们的状态表⽰⼀般有两种形式:
  • 从 [i, j] 位置出发,一系列操作;
  • 从起始位置出发,到达 [i, j] 位置,一系列操作。

这⾥选择第⼆种定义状态表⽰的⽅式:dp[i][j] 表⽰:到达 [i, j] 位置处,最⼩路径和是多少。

  1. 状态转移:简单分析⼀下。如果 dp[i][j] 表⽰到达到达 [i, j] 位置处的最⼩路径和,那么到达[i, j] 位置之前的⼀⼩步,有两种情况:
  • 从 [i - 1, j] 向下⾛⼀步,转移到 [i, j] 位置;
  • 从 [i, j - 1] 向右⾛⼀步,转移到 [i, j] 位置。

由于到 [i, j] 位置两种情况,并且我们要找的是最⼩路径,因此只需要这两种情况下的最⼩值,再加上 [i, j] 位置上本⾝的值即可。也就是: dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

  1. 初始化:可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
  • 辅助结点⾥⾯的值要「保证后续填表是正确的」;
  • 「下标的映射关系」。

在本题中,「添加⼀⾏」,并且「添加⼀列」后,所有位置的值可以初始化为⽆穷⼤,然后让dp[0][1] = dp[1][0] = 1 即可。

  1. 填表顺序:
    根据「状态转移⽅程」的推导来看,填表的顺序就是「从上往下」填每⼀⾏,每⼀⾏「从左往后」。
  2. 返回值:
    根据「状态表⽰」,我们要返回的结果是 dp[m][n]

🚩代码实现

class Solution {
    public int minPathSum(int[][] grid) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0; j <= n; j++)  {
            dp[0][j] = Integer.MAX_VALUE;
        }
        for(int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        dp[0][1] = dp[1][0] = 0;
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j-1];
            }
        }
        return dp[m][n];
    }
}

🌴地下城游戏

🚩题目描述

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

  • 示例 1:

    输入:dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
    输出:7
    解释:如果骑士遵循最佳路径:右 -> 右 -> 下 -> 下 ,则骑士的初始健康点数至少为 7 。
  • 示例 2:
    输入:dungeon = [[0]]
    输出:1
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
    }
}

🚩算法思路

  1. 状态表⽰:

这道题如果我们定义成:从起点开始,到达 [i, j] 位置的时候,所需的最低初始健康点数。那么我们分析状态转移的时候会有⼀个问题:那就是我们当前的健康点数还会受到后⾯的路径的影响。也就是从上往下的状态转移不能很好地解决问题。

这个时候我们要换⼀种状态表⽰:从 [i, j] 位置出发,到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候,后续的最佳状态就已经知晓。

综上所述,定义状态表⽰为:

dp[i][j] 表⽰:从 [i, j] 位置出发,到达终点时所需的最低初始健康点数。

  1. 状态转移⽅程:对于 dp[i][j] ,从 [i, j] 位置出发,下⼀步会有两种选择(为了⽅便理解,设 dp[i] [j] 的最终答案是 x ):
  • ⾛到右边,然后⾛向终点
    那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于右边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i][j + 1] 。通过移项可得: x >= dp[i][j + 1] - dungeon[i][j] 。因为我们要的是最⼩值,因此这种情况下的 x = dp[i][j + 1] - dungeon[i][j] ;
  • ⾛到下边,然后⾛向终点
    那么我们在 [i, j] 位置的最低健康点数加上这⼀个位置的消耗,应该要⼤于等于下边位置的最低健康点数,也就是: x + dungeon[i][j] >= dp[i + 1][j] 。通过移项可得: x >= dp[i + 1][j] - dungeon[i][j] 。因为我们要的是最⼩值,因此这种情况下的 x = dp[i + 1][j] - dungeon[i][j] ;

综上所述,我们需要的是两种情况下的最⼩值,因此可得状态转移⽅程为:dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]

但是,如果当前位置的 dungeon[i][j] 是⼀个⽐较⼤的正数的话, dp[i][j] 的值可能变成 0 或者负数。也就是最低点数会⼩于 1 ,那么骑⼠就会死亡。因此我们求出来的 dp[i][j] 如果⼩于等于 0 的话,说明此时的最低初始值应该为 1 。处理这种情况仅需让 dp[i][j] 与 1 取⼀个最⼤值即可:dp[i][j] = max(1, dp[i][j])

  1. 初始化:可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
  • 辅助结点⾥⾯的值要「保证后续填表是正确的」;
  • 「下标的映射关系」。

在本题中,在 dp 表最后⾯添加⼀⾏,并且添加⼀列后,所有的值都先初始化为⽆穷⼤,然后让dp[m][n - 1] = dp[m - 1][n] = 1 即可。

  1. 填表顺序:
    根据「状态转移⽅程」,我们需要「从下往上填每⼀⾏」,「每⼀⾏从右往左」。
  2. 返回值:
    根据「状态表⽰」,我们需要返回 dp[0][0] 的值

🚩代码实现

class Solution {
    public int calculateMinimumHP(int[][] d) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = d.length;
        int n = d[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int j = 0; j <= n; j++) {
            dp[m][j] = Integer.MAX_VALUE;
        }
        for(int i = 0; i <= m; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = dp[m - 1][n] = 1;
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i][j + 1], dp[i + 1][j]) - d[i][j];
                dp[i][j] = Math.max(dp[i][j], 1);
            }
        }
        return dp[0][0];
    }
}

⭕总结

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

相关文章
|
1月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
51 2
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
99 2
动态规划算法学习三:0-1背包问题
|
2月前
|
数据采集 监控 安全
厂区地图导航制作:GIS技术与路径导航算法融合
在智能化、数字化时代,GIS技术为厂区的运营管理带来了革命性变化。本文探讨了如何利用GIS技术,通过数据采集、地图绘制、路径规划、位置定位和信息查询等功能,打造高效、精准的智能厂区地图导航系统,提升企业的竞争力和管理水平。
80 0
厂区地图导航制作:GIS技术与路径导航算法融合
|
2月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
80 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
2月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
172 0
动态规划算法学习二:最长公共子序列
|
2月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
163 0
|
19天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
25天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
5天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。
|
12天前
|
存储 算法
基于HMM隐马尔可夫模型的金融数据预测算法matlab仿真
本项目基于HMM模型实现金融数据预测,包括模型训练与预测两部分。在MATLAB2022A上运行,通过计算状态转移和观测概率预测未来值,并绘制了预测值、真实值及预测误差的对比图。HMM模型适用于金融市场的时间序列分析,能够有效捕捉隐藏状态及其转换规律,为金融预测提供有力工具。