首页 > 代码库 > 【leetcode】Unique Paths
【leetcode】Unique Paths
Unique Paths
A robot is located at the top-left corner of a m x n grid (marked ‘Start‘ in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish‘ in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
可以推到一下公式，对于m+1,n+1来说，只需要向右走m步，向下走n步，就能到达终点了，我们把向下和向右进行排列，所有的排列数就是结果
因此result=(m+n)!/(m!*n!)
直接求会超出范围，因此化简一下：
化简一下(m+1)(m/2+1)……（m/n+1)
1 class Solution { 2 public: 3 4 int uniquePaths(int m, int n) { 5 6 int result=0; 7 double tmp=1; 8 m--; 9 n--;10 for(int i=0;i<n;i++)11 {12 tmp*=(double)(m)/(i+1)+1;13 }14 15 result=round(tmp);16 return result;17 }18 };
直接用动态规划
1 class Solution { 2 public: 3 4 int uniquePaths(int m, int n) { 5 6 if(m==0||n==0) return 0; 7 8 int dp[101][101]; 9 10 dp[0][0]=1;11 12 for(int i=1;i<m;i++)13 {14 dp[i][0]=1;15 }16 17 for(int j=1;j<n;j++)18 {19 dp[0][j]=1;20 }21 22 for(int i=1;i<m;i++)23 {24 for(int j=1;j<n;j++)25 {26 dp[i][j]=dp[i][j-1]+dp[i-1][j];27 }28 }29 return dp[m-1][n-1];30 }31 };
【leetcode】Unique Paths
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。