public int uniquePaths(int m, int n) { if (m == 1 || n == 1){ return 1; } return uniquePaths(--m, --n); }
时间: 2024-04-28 09:19:19 浏览: 4
这段代码是一个递归函数,用于求解从左上角到右下角的路径数量,其中m和n分别表示网格的行数和列数。如果m或n为1,则只有一条路径。如果m和n都大于1,则递归调用函数,求解从左上角到达(m-1, n)和(m, n-1)的路径数量,然后两者相加,即为从左上角到达(m, n)的路径数量。
不过这段代码有一个问题,就是没有任何终止条件,会导致栈溢出。因此,需要加入终止条件,例如当m或n等于0时返回0。同时,还需要记录已经计算过的路径数量,可以使用一个二维数组来存储。
相关问题
public class ex1 { public int uniquePaths(int m,int n){ int[][] dp = new int[m][n]; for(int i = 0;i < m;i++){ for (int j = 0;j < m;j++){ if(i==0||j==0) dp[i][j] = 1;//第一列置1 else{ dp[i][j] = dp[i-1][j] + dp[i][j-1];//第一行置1 } } } //向下和向右路径和 return dp[m-1][n-1]; } }
这个实现和之前的有些差别,主要是在边界条件上。这里将第一列和第一行的元素全部初始化为 1,因此在状态转移方程中不需要特别处理边界情况。下面是稍微优化后的 Java 版本代码:
```java
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// 初始化第一列和第一行的元素为 1
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 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 static int gcd(int m, int n) 还可以怎么写
`public static int gcd(int m, int n)` 这个方法还可以使用递归来实现。递归方法的基本思路是:如果 m 小于 n,就交换 m 和 n 的值;然后,如果 n 等于 0,就返回 m,否则递归调用 `gcd(n, m % n)`。
下面是使用递归方式实现的代码:
```
public static int gcd(int m, int n) {
if (m < n) {
int temp = m;
m = n;
n = temp;
}
if (n == 0) {
return m;
} else {
return gcd(n, m % n);
}
}
```
递归实现的方式与循环实现的方式相比,代码看起来更加简洁,但是在计算过程中会生成多个调用栈,可能会导致栈溢出的问题。因此,在实际应用中需要注意函数的递归深度。