本文主要是介绍91、动态规划-不同的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
思路：
首先我们可以使用暴力递归解法，无非就是每次向下或者向右看看是否有解法，代码如下：
public class Solution {public int uniquePaths(int m, int n) {return findPaths(0, 0, m, n);}private int findPaths(int i, int j, int m, int n) {// 如果越界，返回0if (i >= m || j >= n) {return 0;}// 当到达右下角时，返回1if (i == m - 1 && j == n - 1) {return 1;}// 否则，路径数是从下方和右方到达当前位置的路径数之和return findPaths(i + 1, j, m, n) + findPaths(i, j + 1, m, n);}
}
然后根据这个递归来解动态规划
代码如下：
public class Solution {public int uniquePaths(int m, int n) {// 初始化dp表，所有值默认为0int[][] dp = new int[m][n];// 初始化第一行和第一列的所有位置for (int i = 0; i < m; i++) {dp[i][0] = 1;}for (int j = 0; j < n; j++) {dp[0][j] = 1;}// 填充dp表的其余部分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];}
}
这篇关于91、动态规划-不同的路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
