首页 > 其他分享 >lintcode: Unique Paths

lintcode: Unique Paths

时间:2022-12-01 19:06:58浏览次数:57  
标签:Paths cnt return int lintcode robot ret integer Unique


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?

Note m and n will be at most 100.

1.方法1

采用组合数学的方法。
这个问题在组合数学中有计算公式:C(m+n-2,m-1).因为从左上角到右下角一共会走m+n-2步,只要选中横向(或纵向)的m-1(或n-1)步,行进的路线就会固定。
现在就要求C(m+n-2,m-1)这个怎么编程求出。

组合数C(m,n)的求法:
即在m个物体中选择n个。

  • 假设m个物体中的的物体a被选中,那么接下来有C(m-1,n-1)种方法;
  • 假设物体a不会被选,那么接下来有C(m-1,n)中方法。
    所以C(m,n)=C(m-1,n-1)+C(m-1,n);

先用递归发现超时。
用动态规划实现。

class Solution {
public:
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/

int uniquePaths(int m, int n) {
// wirte your code here
int cnt[m+n][m];
for(int i=1;i<=m+n-2;i++){
cnt[i][0]=1;
}

for(int i=1;i<=m+n-2;i++){
for(int j=1;j<=m-1;j++){
if(i==j){
cnt[i][j]=1;
continue;
}else if(i<j){
cnt[i][j]=0;
}else{
cnt[i][j]=cnt[i-1][j-1]+cnt[i-1][j];
}

}
}

return cnt[m+n-2][m-1];
}
};

2.方法2

cnt[m][n] 表示到位置[m][n] 的路径数。
而到位置[m][n] 只能从[m-1][n] 和[m][n-1] 两个位置到达

所以cnt[m][n]=cnt[m-1][n] + cnt[m][n-1] ;

class Solution {
public:
/**
* @param n, m: positive integer (1 <= n ,m <= 100)
* @return an integer
*/
int uniquePaths(int m, int n) {
if (m < 1 || n < 1) {
return 0;
}

vector<vector<int> > ret(m, vector(n, 1));

for (int i = 1; i != m; ++i) {
for (int j = 1; j != n; ++j) {
ret[i][j] = ret[i - 1][j] + ret[i][j - 1];
}
}

return ret[m - 1][n - 1];
}
};


标签:Paths,cnt,return,int,lintcode,robot,ret,integer,Unique
From: https://blog.51cto.com/u_15899184/5903596

相关文章

  • lintcode:Trailing Zeros
    15:00StartWriteanalgorithmwhichcomputesthenumberoftrailingzerosinnfactorial.Example11!=39916800,sotheoutshouldbe2ChallengeO(logN)time......
  • lintcode:Update Bits
    Giventwo32-bitnumbers,NandM,andtwobitpositions,iandj.WriteamethodtosetallbitsbetweeniandjinNequaltoM(eg,Mbecomesasubstring......
  • lintcode: Fast Power
    Calculatethea^b%bwherea,bandnareall32bitintegers.ExampleFor231%3=2For1001000%1000=0ChallengeO(logn)思路参见我的博客​​幂模运算​​cla......
  • lintcode:Binary Tree Serialization
    Designanalgorithmandwritecodetoserializeanddeserializeabinarytree.Writingthetreetoafileiscalled‘serialization’andreadingbackfromthe......
  • lintcode: N-Queens
    Then-queenspuzzleistheproblemofplacingnqueensonann×nchessboardsuchthatnotwoqueensattackeachother.Givenanintegern,returnalldistincts......
  • lintcode:Permutations
    Givenalistofnumbers,returnallpossiblepermutations.ChallengeDoitwithoutrecursion.1.递归classSolution{public:/***@paramnums:Alistofi......
  • lintcode:Subsets
    Givenasetofdistinctintegers,returnallpossiblesubsets.ChallengeCanyoudoitinbothrecursivelyanditeratively?1.18sclassSolution{public:/**......
  • lintcode: Permutations II
    Givenalistofnumberswithduplicatenumberinit.Findalluniquepermutations.可以见我的博文​​全排列实现​​classSolution{public:/***@paramnu......
  • lintcode: Subsets II
    Givenalistofnumbersthatmayhasduplicatenumbers,returnallpossiblesubsets1.先排序;再按求Subsets一样的做法,只是添加前检查是否已经存在。耗时171mscla......
  • lintcode:Subarray Sum Closest
    Givenanintegerarray,findasubarraywithsumclosesttozero.Returntheindexesofthefirstnumberandlastnumber.ExampleGiven[-3,1,1,-3,5],retur......