首页 > 代码库 > leetcode第一刷_Unique Paths

leetcode第一刷_Unique Paths

从左上到右下,只能向右或向下,问一共有多少种走法。

这个问题当然可以用递归和dp来做,递归的问题是很可能会超时,dp的问题是需要额外空间。

其实没有其他限制条件的话,这个问题有个很简单的解法。给定一个格子,假设是m*n的,从左上角走到右下角的总步数是确定了的,(m+n-2)嘛,即在竖直方向一定要走m-1步,在水平方向一定要走n-1步。那有多少种解法就相当于确定什么时候往下走,什么时候往右走,也即相当于从这m+n-2步中,挑选出m-1步有多少种挑法,因为剩下的肯定要往右走嘛。问题实际上就是求c(m+n-2 , m-1),当然也等于c(m+n-2,n-1),具体用哪一个可以挑个小的好算的。

int getNum(int sum, int part){
    if(part==0||part==sum)
        return 1;
    long long mpart = 1;
    for(int i=2;i<=part;i++)
        mpart *= i;
    long long msum = 1;
    for(int i=sum-part+1;i<=sum;i++)
        msum *= i;
    return (int)(msum/mpart);
}


class Solution {
public:
    int uniquePaths(int m, int n) {
        return getNum(m+n-2, min(m-1, n-1));
    }
};