LeetCode题目:Unique Paths

By | 2012 年 11 月 4 日

只计算个数的话有简单算法,如果是m行,n列的矩阵,机器人从左上走到右下总共需要的步数是n + m – 2,其中向下走的步数是m -1。因此问题变成了在n + m -2个操作中,选择m – 1个时间点向下走,的选择方式有多少种。
那就是:Cm+n-2m-1
程序的话,加上一点trick让其不越界就行了。



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.



代码:8ms过大集合

class Solution {
public:
    long long factor(int n,int start = 1) {
        long long  ret = 1;
        for(int i = start; i <= n; ++i)
            ret *= i;
        return ret;
    }
    int uniquePaths(int m, int n) {
        int right = n - 1;
        int down = m - 1;
        int total = right + down;
        int ba = max(right,down);
        long long ret = factor(total,ba + 1);
        ret /= factor(total - ba);
        return ret;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注