class Solution { public int uniquePaths(int m, int n) { int[] pre = new int[n]; int[] cur = new int[n]; Arrays.fill(pre, 1); Arrays.fill(cur,1); for (int i = 1; i < m;i++){ for (int j = 1; j < n; j++){ cur[j] = cur[j-1] + pre[j]; } pre = cur.clone(); } return pre[n-1]; } }
时间: 2024-01-28 21:05:37 浏览: 82
redis数据结构之intset的实例详解
这段代码是用来计算从一个矩形的左上角到右下角的所有不同路径数量。以下是一些可以改善代码的建议:
1. 可以使用一个一维数组来代替两个一维数组。因为在计算每一行的路径时,只需要前一行的结果,这可以使用一个一维数组来实现。
2. 可以使用滚动数组的技巧来节省空间。因为在计算每一行的路径时,只需要前一行的结果,所以可以使用滚动数组来避免使用整个数组。
3. 可以使用数学公式来计算路径数量,而不是使用动态规划算法。因为路径数量可以使用组合数公式计算,这将大大提高计算效率。
下面是经过这些改善后的代码:
```
class Solution {
public int uniquePaths(int m, int n) {
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];
}
}
return dp[n - 1];
}
}
```
这样,代码将更加简洁、高效。
阅读全文