首页 > 代码库 > leetcode 62. Unique Paths
leetcode 62. Unique Paths
第一种最简单的方法：递归求解：
- 要求uniquePaths(m,n)=uniquePaths(m-1,n)+uniquePaths(m,n-1)（m>1,n>1）
- uniquePaths(m,n)=uniquePaths(m-1,n)（,n==1）
- uniquePaths(m,n)=uniquePaths(m,n-1)（m==1）
- 终止条件为： m=1,n=1,uniquePaths(m,n)=1;
int uniquePaths(int m, int n) { if(m==1&&n==1) return 1; if(m==1) return uniquePaths(m,n-1); if(n==1) return uniquePaths(m-1,n); if(m>1&&n>1) return uniquePaths(m-1,n)+uniquePaths(m,n-1);}
但是递归方法太费时间,out
第二种方法，动态规划的思想：
- 建立一个动态规划数组dp[m][n], dp[m][n]=dp[m][n-1]+dp[m-1][n-1];
vector<vector<int>> dp(m,vector<int> (n,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];时间复杂度为O(n^2),cost m*nspace
第三种方法： 数学计算法：
如果有4*6 个格子，相当于有3个下，5个右，进行排列组合。得到排列的数目就ok
总共有(m+n)! / (m! * n!)种排列方法
- m+n个数(m+n)!中排列方式
- 除去内部相同m 个下和n个右，
leetcode 62. Unique Paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。