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

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


🎋前言

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

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

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

🎋不同路径

🚩题目描述:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

  • 示例 1:

    输入:m = 3, n = 7
    输出:28
  • 示例 2:
    输入:m = 3, n = 2
    输出:3
    解释:
    从左上角开始,总共有 3 条路径可以到达右下角。
    1.向右 -> 向下 -> 向下
    2.向下 -> 向下 -> 向右
    3.向下 -> 向右 -> 向下
  • 示例 3:
    输入:m = 7, n = 3
    输出:28
  • 示例 4:
    输入:m = 3, n = 3
    输出:6
class Solution {
    public int uniquePaths(int m, int n) {
    }
}

🚩算法思路:

  1. 状态表⽰:对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:
  • 从 [i, j] 位置出发,进行一系列操作;
  • 从起始位置出发,到达 [i, j] 位置,进行一系列操作。
  • 这⾥选择第⼆种定义状态表⽰的⽅式:
  • dp[i][j] 表⽰:⾛到 [i, j] 位置处,⼀共有多少种⽅式。
  1. 状态转移⽅程:简单分析⼀下。如果 dp[i][j] 表⽰到达 [i, j] 位置的⽅法数,那么到达 [i, j] 位置之前的⼀⼩步,有两种情况:
  • 从 [i, j] 位置的上⽅( [i - 1, j] 的位置)向下⾛⼀步,转移到 [i, j] 位置;
  • 从 [i, j] 位置的左⽅( [i, j - 1] 的位置)向右⾛⼀步,转移到 [i, j] 位置。
  • 由于我们要求的是有多少种⽅法,因此状态转移⽅程就呼之欲出了:
  • dp[i][j] = dp[i - 1] [j] + dp[i][j - 1] 。
  1. 初始化:可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:
  • 辅助结点⾥⾯的值要「保证后续填表是正确的」;
  • 「下标的映射关系」。
    在本题中,「添加⼀⾏」,并且「添加⼀列」后,只需将 dp[0][1] 的位置初始化为 1 即可。
  1. 填表顺序:
    根据「状态转移⽅程」的推导来看,填表的顺序就是「从上往下」填每⼀⾏,在填写每⼀⾏的时候「从左往右」。
  2. 返回值:
    根据「状态表⽰」,我们要返回 dp[m][n] 的值

🚩代码实现

class Solution {
  public int uniquePaths(int m, int n) {
    // 1. 创建 dp 表
    // 2. 初始化
    // 3. 填表
    // 4. 返回值
    int[][] dp = new int[m + 1][n + 1];
    dp[0][1] = 1;
    for(int i = 1; i <= m; i++) // 从上往下每⼀⾏
      for(int j = 1; j <= n; j++) // 从左往右填写每⼀⾏
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    return dp[m][n];
  }
}

🎋不同路径二

🚩题目描述

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

  • 示例 1:

    输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
    输出:2
    解释:3x3 网格的正中间有一个障碍物。
    从左上角到右下角一共有 2 条不同的路径:
    1.向右 -> 向右 -> 向下 -> 向下
    2.向下 -> 向下 -> 向右 -> 向右
  • 示例 2

    输入:obstacleGrid = [[0,1],[0,0]]
    输出:1
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    }
}

🚩算法思路

本题为不同路径的变型,只不过有些地⽅有「障碍物」,只要在「状态转移」上稍加修改就可解决。

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

这⾥选择第⼆种定义状态表⽰的⽅式:dp[i][j] 表⽰:⾛到 [i, j] 位置处,⼀共有多少种⽅式。

  1. 状态转移:简单分析⼀下。如果 dp[i][j] 表⽰到达 [i, j] 位置的⽅法数,那么到达 [i, j] 位置之前的⼀⼩步,有两种情况:
  • 从 [i, j] 位置的上⽅( [i - 1, j] 的位置)向下⾛⼀步,转移到 [i, j] 位置;
  • 从 [i, j] 位置的左⽅( [i, j - 1] 的位置)向右⾛⼀步,转移到 [i, j] 位置。

但是, [i - 1, j] 与 [i, j - 1] 位置都是可能有障碍的,此时从上⾯或者左边是不可能到达 [i, j] 位置的,也就是说,此时的⽅法数应该是0。

由此我们可以得出⼀个结论,只要这个位置上「有障碍物」,那么我们就不需要计算这个位置上的值,直接让它等于 0 即可。

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

在本题中,添加⼀⾏,并且添加⼀列后,只需将 dp[1][0] 的位置初始化为 1 即可。

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

🚩代码实现

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][] = 1;
        for(int i = 1; i <= m ; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i - 1][j - 1] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}

🌲珠宝的最高价值

🚩题目描述

现有一个记作二维矩阵 frame 的珠宝架,其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为:

只能从架子的左上角开始拿珠宝

每次可以移动到右侧或下侧的相邻位置

到达珠宝架子的右下角时,停止拿取

注意:珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝,比如 frame = [[0]]。

  • 示例 1:
    输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
class Solution {
    public int jewelleryValue(int[][] frame) {
        
    }
}

🚩算法思路:

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

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

dp[i][j] 表⽰:⾛到 [i, j] 位置处,此时的最⼤价值。

  1. 状态转移⽅程:对于 dp[i][j] ,我们发现想要到达 [i, j] 位置,有两种⽅式:
  • 从 [i, j] 位置的上⽅ [i - 1, j] 位置,向下⾛⼀步,此时到达 [i, j] 位置能拿到的礼物价值为 dp[i - 1][j] + grid[i][j] ;
  • 从 [i, j] 位置的左边 [i, j - 1] 位置,向右⾛⼀步,此时到达 [i, j] 位置能拿到的礼物价值为 dp[i][j - 1] + grid[i][j]

我们要的是最⼤值,因此状态转移⽅程为:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] 。

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

在本题中,「添加⼀⾏」,并且「添加⼀列」后,所有的值都为 0 即可。

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

🚩代码实现

class Solution {
    public int jewelleryValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j-1];
        return dp[m][n];
    }
}

⭕总结

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

相关文章
|
5天前
|
算法
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
24 1
|
11天前
|
算法
优选算法|【双指针】|202.快乐数
优选算法|【双指针】|202.快乐数
|
11天前
|
算法
算法系列--动态规划--背包问题(5)--二维费用背包问题(上)
算法系列--动态规划--背包问题(5)--二维费用背包问题(上)
16 0
|
11天前
|
算法
算法系列--动态规划--背包问题(4)--完全背包拓展题目(上)
算法系列--动态规划--背包问题(4)--完全背包拓展题目(上)
18 0
|
11天前
|
算法
算法系列--动态规划--背包问题(3)--完全背包介绍(下)
算法系列--动态规划--背包问题(3)--完全背包介绍(下)
14 0
|
11天前
|
存储 算法
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)(下)
算法系列--动态规划--⼦数组、⼦串系列(数组中连续的⼀段)(1)
15 0
|
30天前
|
传感器 算法 计算机视觉
基于肤色模型和中值滤波的手部检测算法FPGA实现,包括tb测试文件和MATLAB辅助验证
该内容是关于一个基于肤色模型和中值滤波的手部检测算法的描述,包括算法的运行效果图和所使用的软件版本(matlab2022a, vivado2019.2)。算法分为肤色分割和中值滤波两步,其中肤色模型在YCbCr色彩空间定义,中值滤波用于去除噪声。提供了一段核心程序代码,用于处理图像数据并在FPGA上实现。最终,检测结果输出到&quot;hand.txt&quot;文件。
|
1月前
|
机器学习/深度学习 算法 计算机视觉
基于yolov2深度学习网络的视频手部检测算法matlab仿真
基于yolov2深度学习网络的视频手部检测算法matlab仿真
|
1月前
|
算法
【MATLAB】语音信号识别与处理:移动中位数滤波算法去噪及谱相减算法呈现频谱
【MATLAB】语音信号识别与处理:移动中位数滤波算法去噪及谱相减算法呈现频谱
23 2
|
1月前
|
算法
【MATLAB】语音信号识别与处理:一维信号NLM非局部均值滤波算法去噪及谱相减算法呈现频谱
【MATLAB】语音信号识别与处理:一维信号NLM非局部均值滤波算法去噪及谱相减算法呈现频谱
39 1

热门文章

最新文章