代码随想录 62.不同路径

思路方法一、深度优先搜索可以使用图论里的深度优先搜索枚举出来有多少种路径时间复杂度过大不可行。1.题目中说机器人每次只能向下或者向右移动一步因此可以将机器人走过的路径抽象为一棵二叉树而叶子节点就是终点如下图所示。2.因此将问题抽象为求二叉树的叶子节点的个数。结果超时。因为深搜要遍历整棵二叉树而这棵树的深度就是m n - 1深度按从1开始计算那么二叉树的节点个数就是2^(m n - 1) - 1。因此深搜的算法会遍历整个满二叉树近似而指数级别的时间复杂度过大。方法二、动态规划机器人从00位置出发到m - 1,n - 1终点。动规五部曲:1.确定dp数组dp table及其下标的含义dp[i][[j]表示从00出发到i,j有dp[i][j]条不同的路径。2.确定递推公式想要求dp[i][j]只能由两个方向推导出来即dp[i - 1][j]和dp[i][j - 1]。此时再回顾一下dp[i - 1][j]和dp[i][j - 1]的含义dp[i - 1][j]表示从00的位置到i - 1,j有几条路径,dp[i][j - 1]同理。因此很自然dp[i][j] dp[i - 1][j] dp[i][j - 1]因为dp只有这两个方向过来。3.dp数组如何初始化首先dp[i][0]一定都是1因为从00到i0的路径一定只有一条dp[0][j]也同理。所以初始化代码为for (int i 0; i m; i) dp[i][0] 1; for (int j 0; j n; j) dp[0][j] 1;4.确定遍历顺序看一下递推公式dp[i][j] dp[i - 1][j] dp[i][j - 1]dp[i][j]都是从其上方和左方推导而来那么从左到右一层一层遍历就可以了。这样就可以保证推导dp[i][j]的时候dp[i - 1][j]和dp[i][j - 1]是一定有数值的。5.举例推导dp数组如下图所示。附代码class Solution { public int uniquePaths(int m, int n) { int[][] dp new int[m][n]; //初始化 for(int i 0;i m;i ){ dp[i][0] 1; } for(int i 0;i n;i ){ dp[0][i] 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 - 1][n - 1]; } }//状态压缩当当前状态只依赖于有限的前置状态时都可以考虑状态压缩 class Solution { public int uniquePaths(int m, int n) { //在二维dp数组中当前值的计算只依赖正上方和正左方因此可以压缩成一维数组 //表示当前行第j列的路径数 int[] dp new int[n]; //初始化第一行只能从正左方跳过来所以只有一条路径。 Arrays.fill(dp,1); for(int i 1;i m;i){ //第一列也只有一条路不用迭代所以从第二列开始 for(int j 1;j n;j){ dp[j] dp[j - 1]; //dp[j] dp[j](上一行第j列的值) dp[j - 1](当前行第j - 1列的值) } } return dp[n - 1]; } }方法三数论方法。如下图所示可以看出一共mn的话无论怎么走走到终点都需要m n - 2步。在这m n - 2步中一定有m - 1步是要向下走的不用管什么时候向下走。有几种走法可以转化为给定m n - 2个不同的数随便取m - 1个数有几种取法。即把问题转化为组合问题。答案如下图所示同时在求组合的过程中要防止两个int相乘溢出。所以不能把算式的分子都算出来分母都算出来再做除法而是在计算分子的时候不断除以分母(C代码如下图所示)class Solution { public: int uniquePaths(int m, int n) { long long numerator 1; // 分子 int denominator m - 1; // 分母 int count m - 1; int t m n - 2; while (count--) { numerator * (t--); while (denominator ! 0 numerator % denominator 0) { numerator / denominator; denominator--; } } return numerator; } };ACM模式import java.util.Scanner; class Solution { public int uniquePaths(int m, int n) { int[][] dp new int[m][n]; for (int i 0; i m; i) { dp[i][0] 1; } for (int i 0; i n; i) { dp[0][i] 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 - 1][n - 1]; } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取网格的行数和列数 int m scanner.nextInt(); int n scanner.nextInt(); // 计算不同路径数 Solution solution new Solution(); int result solution.uniquePaths(m, n); System.out.println(result); scanner.close(); } }