【第38天】不同路径数问题 | 网格 dp 入门

本文已收录于专栏 🌸《Java入门一百例》🌸

序、专栏前言

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

一、网格模型

   网格模型是一个很经典的模型，也可以称之为数字三角形模型。其一般形态就是在一个二维的网格中，以左上角为起点，到右下角为终点，只能往下走或者往右走。求得这个过程中可以获取的不同路径数或者权值最大最小问题，当然如何移动也要根据题意来分析，在转移时亦是如此。今天将带来两道最入门的网格dp入门题。

二、【例题1】

1、题目描述

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

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

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

2、解题思路

   定义 $f[i][j]$ 为走到 $i$ 行 $j$ 列的不同路径数，显然 $i$ 行 $j$ 列只能从$i-1$ 行 $j$ 列和$i$ 行 $j-1$ 列走过来，那么具有转移方程：
$$f[i][j]=f[i-1][j]+f[i][j-1]$$
初始化时$f[1][1]$应该等于1，答案即是$f[m][n]$

3、模板代码

class Solution {public int uniquePaths(int m, int n) {int[][] f=new int[m+1][n+1];f[1][1]=1;for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){if(i==1&&j==1) continue;f[i][j]=f[i-1][j]+f[i][j-1];}}return f[m][n];}
}

使用滚动数组优化:

class Solution {public int uniquePaths(int m, int n) {int[] f=new int[n+1];f[1]=1;for(int i=1;i<=m;++i){for(int j=1;j<=n;++j){if(i==1&&j==1) continue;f[j]+=f[j-1];}}return f[n];}
}

4、代码解析

滚动数组优化，也是二维dp里常用的优化方式，可以帮忙我们压缩一维空间，不太理解暂时不建议深究。
为了防止边界越界问题，这里大家 $i$ $j$ 都从1开始，如果从0的话在转移时会出现越界。

5.原题链接

不同路径

三、【例题2】

1、题目描述

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

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

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

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

2、解题思路

转移方程和上面是相同的，不同由于存在障碍物，只有在 $i,j$ 不是障碍物时，我们才进去转移才行，同样为了防止边界越界，我们 dp 时下标同样从1开始。

3、模板代码

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

4、代码解析

注意起点有可能有石头，初始化时需要进行判断。

5.原题链接

不同路径||

三、推荐专栏

🌌《零基础学算法100天》🌌

四、课后习题

序号	题目链接	难度评级
1	最小路径和	3

👇 学习有疑问？👇