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

古城微笑少年丶 2024-04-17 10:45 78阅读 0赞

#### 文章目录 ####

*  ?前言
 *  ?\[不同路径\](https://leetcode.cn/problems/unique-paths/)
 *   *  ?题目描述：
     *  ?算法思路：
     *  ?代码实现
 *  ?\[不同路径二\](https://leetcode.cn/problems/unique-paths-ii/description/)
 *   *  ?题目描述
     *  ?算法思路
     *  ?代码实现
 *  ?\[珠宝的最高价值\](https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/)
 *   *  ?题目描述
     *  ?算法思路：
     *  ?代码实现
 *  ⭕总结

## ?前言 ##

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

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

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

## ?[不同路径][Link 1] ##

### ?题目描述： ###

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

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

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

*  示例 1：  
    ![在这里插入图片描述][19fe6c272c9d41cb86063ce133f72700.png]  
    输入：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 即可。
2.  填表顺序：  
    根据「状态转移⽅程」的推导来看，填表的顺序就是「从上往下」填每⼀⾏，在填写每⼀⾏的时候「从左往右」。
3.  返回值：  
    根据「状态表⽰」，我们要返回 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];
    	}
    }

## ?[不同路径二][Link 2] ##

### ?题目描述 ###

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

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

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

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

*  示例 1：  
    ![在这里插入图片描述][f8f1acc104f8495d921abbbd2fae0139.png]  
    输入：obstacleGrid = \[\[0,0,0\],\[0,1,0\],\[0,0,0\]\]  
    输出：2  
    解释：3x3 网格的正中间有一个障碍物。  
    从左上角到右下角一共有 2 条不同的路径：  
    1.向右 -> 向右 -> 向下 -> 向下  
    2.向下 -> 向下 -> 向右 -> 向右
 *  示例 2  
    ![在这里插入图片描述][b73d3e13b7e7428091b25c347ad7bad8.png]  
    输入：obstacleGrid = \[\[0,1\],\[0,0\]\]  
    输出：1

class Solution {
        
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        
    
        }
    }

### ?算法思路 ###

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

这⾥选择第⼆种定义状态表⽰的⽅式：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];
        }
    }

## ?[珠宝的最高价值][Link 3] ##

### ?题目描述 ###

现有一个记作二维矩阵 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) {
            
        }
    }

### ?算法思路： ###

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

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\] 。

在本题中，「添加⼀⾏」，并且「添加⼀列」后，所有的值都为 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];
        }
    }

## ⭕总结 ##

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

[Link 1]: https://leetcode.cn/problems/unique-paths/
[19fe6c272c9d41cb86063ce133f72700.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/803bf78ea73746f2890359dc30403b28.png
[Link 2]: https://leetcode.cn/problems/unique-paths-ii/description/
[f8f1acc104f8495d921abbbd2fae0139.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/86b93a38c9e643f3bd6f895854d9cec9.png
[b73d3e13b7e7428091b25c347ad7bad8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/0811478675a243f88590024fa798c359.png
[Link 3]: https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/