LeetCode 62. 不同路径
程序员文章站
2022-07-12 12:58:32
...
题目地址:https://leetcode-cn.com/problems/unique-paths/description/
思路:递归或者动态规划
超时代码:
class Solution {
public int uniquePaths(int m, int n) {
// 在网格边界的格子只能有一种走法
if (m == 1 || n == 1) {
return 1;
}
// m,n这个位置只能从(m - 1 , n)和(m, n - 1)移动而来
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
}
备忘录法
class Solution {
public static int[][] grid = new int[110][110];
public int uniquePaths(int m, int n) {
if (grid[m][n] != 0)
return grid[m][n];
if (m == 1 || n == 1) {
return 1;
}
return grid[m][n] = uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
}
动态规划
class Solution {
public static int[][] grid = new int[110][110];
public int uniquePaths(int m, int n) {
for (int i = 1; i <= n ; i++) {
for (int j = 1; j <= m ; j++) {
if (i == 1 || j == 1)
grid[i][j] = 1;
else
grid[i][j] = grid[i][j-1] + grid[i-1][j];
}
}
return grid[n][m];
}
}
上一篇: Leetcode 62. 不同路径
下一篇: RecycleView瀑布流没有数据
推荐阅读
-
leadcode的Hot100系列--62. 不同路径--简单的动态规划
-
荐 LeetCode 120. 三角形最小路径和 | Python
-
【每日一道算法题】Leetcode之longest-increasing-path-in-a-matrix矩阵中的最长递增路径问题 Java dfs+记忆化
-
Nginx配置实例-反向代理实例:根据访问的路径跳转到不同端口的服务中
-
荐 LeetCode 112. 路径总和 | Python
-
动态规划_leetcode.64.最小路径和
-
63. 不同路径 II
-
LeetCode 63. 不同路径 II
-
63. 不同路径 II
-
[leetcode]63. 不同路径 II