排列组合基础- 走方格方法数,leetcode 62. Unique Paths

国内高佣广告联盟 熊掌联运广告联盟 最新域名优惠/VPS优惠/免备案CDN活动

这边给大家介绍一道有关高中数学的排列组合问题
参考题目: 62. Unique Paths

题意: 给定m*n个方格,机器人站在左上角要走到右下角,只能往右边或下边走,
全部有几种走法?

譬如说:

Input: m = 3, n = 2
Output: 3
说明:
三种走法为
1. 右右下
2. 右下右
3. 下右右

其实这一题如果数学好的话就很简单,
有m*n个方格,要走到右下角需要
往右走m-1步,
往下走n-1步,
相当于是m-1个「右」和n-1个「下」的文字排列,
方法数为C(m+n-2,m-1)(或C(m+n-2,n-1))

至于要如何计算组合数C(n,k)呢?
有两种方法:
一种是用可以支援大数运算的语言,如python,
用乘法的公式C(n,k)=(n!)/[(n-k)!(k!)]硬算,不怕溢位

若用c++的话则可以用动态规划的方法避免溢位(可参考leetcode- 119. Pascal’s Triangle II)

c++解法

class Solution {
public:
    long long Cnk(int n, int k) {
        vector<long long> pas(k+1, 1);
        for(int i=1; i<n; i++){
            for(int j=min(i,k); j>0;j--){
                pas[j]+=pas[j-1];
            }
        }
        return pas[k];
    }
    int uniquePaths(int m, int n) {
        return Cnk(m+n-2,min(m-1, n-1));
    }
};

python 解法

class Solution:
    def Cnk(self, n, k):
        ans = 1
        for i in range(k):
            ans *= n-i
        for i in range(k):
            ans //= i+1
        return ans
    def uniquePaths(self, m: int, n: int) -> int:
         return self.Cnk(m+n-2,m-1)

或者可以写得更简洁:

class Solution:
    def Cnk(self, n, k):
        return factorial(n)//factorial(n-k)//factorial(k)
    def uniquePaths(self, m: int, n: int) -> int:
         return self.Cnk(m+n-2,m-1)

推荐:
发点PT邀请码 *62

hjvn2211445大佬: 有的站发了临时药 顺便清一波其他的 没什么大站,要的发 带ID的数据/设备图。 随缘发保留不发权利 如果有大佬能发U2和CHD的,送我一个吧,没有就随缘了 ccfbits…

简介卡特兰数(catalan number)- leetcode 96. Unique Binary Search Trees

卡特兰数在组合学经常用于各种计数问题,可参考维基百科-卡塔兰数 卡特兰数的定义为Cn = C(2n,n)/(n+1), 递迴定义为 譬如前十项卡特兰数为1, 1, 2, 5, 14, 42, 132,…

搬瓦工DC6好像路由炸了

kerui大佬: 网站告警,然后发现连不上,在DC4和DC3 节点上 ping都丢包严重,反倒是国内的ping丢包低一点。。。 找了一个测速的节点,也是这种情况 [email protected]:~…

有感于上网代理违法

这包子上台之后就是在开倒车! 大街上各种标语条幅找到点WEN GE的感觉没? 我们的目标就是曹县

这个发财的机会我想让给需要的人!!!!

以下是原文和翻译后的。。。。。。。。。。。。。。。。。。 这么好的机会我就不要了。。。。。。。。。。。。。。。。。 机会留给楼下了 身份证手持L照都发过去,马上就能拿100W 好嗨哟,感觉人生已经达到…