橙色系网站,重庆景点图片高清图片,平度网站建设ld4,黑龙江省题目出处
62-不同路径-题目出处
题目描述 个人解法 思路#xff1a; todo代码示例#xff1a;#xff08;Java#xff09; todo复杂度分析 todo官方解法
62-不同路径-官方解法
方法1#xff1a;动态规划 思路#xff1a; 代码示例#xff1a;#xff08;Java…题目出处
62-不同路径-题目出处
题目描述 个人解法 思路 todo代码示例Java todo复杂度分析 todo官方解法
62-不同路径-官方解法
方法1动态规划 思路 代码示例Java public class Solution1 {public int uniquePaths(int m, int n) {int[][] f new int[m][n];for (int i 0; i m; i) {f[i][0] 1;}for (int j 0; j n; j) {f[0][j] 1;}for (int i 1; i m; i) {for (int j 1; j n; j) {f[i][j] f[i - 1][j] f[i][j - 1];}}return f[m - 1][n - 1];}}
此外由于 f(i,j) 仅与第 i 行和第 i−1 行的状态有关因此我们可以使用滚动数组代替代码中的二维数组使空间复杂度降低为 O(n)。
public class Solution2 {public int uniquePaths(int m, int n) {int[] f new int[n];for (int i 0; i n; i) {f[i] 1;}for (int i 1; i m; i) {for (int j 1; j n; j) {f[j] f[j - 1];}}return f[n - 1];}}复杂度分析 方法2:组合数学 思路 代码示例Java public class Solution3 {public int uniquePaths(int m, int n) {long ans 1;for (int x n, y 1; y m; x, y) {ans ans * x / y;}return (int) ans;}}复杂度分析 考察知识点
收获
Gitee源码位置
62-不同路径-源码
