Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Unique Paths

Leetcode algorithms 第 62 题: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.

解答

从左上角走到右下角的方法数,每次只能向右或者向下。可以使用动态规划解决,但更直接的答案是C(m+n, n),其中C为组合数。

利用组合数的计算公式直接进行求解:

C(m, n) = m * (m-1) * … * (m-n+1) / n!

为了避免溢出,求组合数的过程中随时除去分子分母的最大公约数。

具体代码如下:

class Solution {
public:
    long long gcd(long long a, long long b)
    {
        for(long long t; t = a % b; a = b, b = t);
        return b;
    }
    int uniquePaths(int m, int n) {
        m--, n--;
        if (m < n) swap(m, n);
        m += n;
        long long a = 1, b = 1;
        for (int i = 0; i < n; i++)
        {
            a *= m - i, b *= n - i;
            long long g = gcd(a, b);
            a /= g, b /= g;
        }
        return a / b;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论