有關(guān)排列組合的一道算法題

一、題目內(nèi)容

廢話不多說，先上題目：

有一個(gè) n × m 的網(wǎng)格，左下角為A，右上角為B，規(guī)定每次只能走一步，并且方向只能是向上或者向右，求A到B共有多少種走法？(例如一個(gè)日字形的格子就是一個(gè)2 × 1的網(wǎng)格，共有3種走法)并用Javascript寫出程序算法。

大家可以先思考一下怎么做，再去看我的方法。

二、解決方法

這個(gè)問題我想了很久，一直在走彎路，其實(shí)用一個(gè)抽象的數(shù)學(xué)方法就可以很輕松解決這個(gè)問題。

現(xiàn)在你可以把向右移動(dòng)想象成記錄一個(gè)數(shù)字1，把向上移動(dòng)抽象成記錄一個(gè)數(shù)字0，并且這些數(shù)字是按順序排列的。

看到這里我相信聰明的小伙伴已經(jīng)想到了如何解決這個(gè)問題。

這個(gè)問題可以抽象成n個(gè)0和m個(gè)1的不同排列的總數(shù)。比如2 × 2的網(wǎng)格就是2個(gè)0和2個(gè)1的所有不同排列的數(shù)量，也就是1100，1010，1001，0110，0101，0011。

進(jìn)而，我們可以把問題抽象成從(m + n)個(gè)0中，隨意抽取m個(gè)0并將它改為1的不同方法數(shù)，是不是覺得問題很熟悉，沒錯(cuò)！就是高中的排列組合。我先把公式亮出來??：

C(m, n + m) = (n + m)!/(m! * n!)

想先復(fù)習(xí)一下排列組合知識(shí)的同學(xué)可以參見下一節(jié)。

三、Javascript代碼描述

以上的結(jié)果用JS的描述，如下：

function getMethods(n, m) {
  // 定義一個(gè)求階乘的輔助函數(shù)
  function factorial(x) {
    if (x === 0) {
      return 1
    } else {
      return factorial(x -1) * x
    }
  }
  return factorial(m + n)/(factorial(m) * factorial(n))
}

如果小伙伴有好的算法，可以留言交流！

四、排列組合

簡(jiǎn)單地講一下排列和組合。

排列

先舉個(gè)栗子（以下n，m均為正整數(shù)），從n個(gè)含有標(biāo)有不同數(shù)字小球的袋子里，按順序抽取n個(gè)小球，且抽取后不再放入袋子里。第一次抽的時(shí)候，有n種可能；第二次抽的時(shí)候有n - 1種可能，以此類推，抽完n個(gè)小球總共的不同排列個(gè)數(shù)為n!。

如果條件不變，只把抽取的小球個(gè)數(shù)改為m（m <= n）個(gè)，結(jié)果也就變成：

n × (n - 1) × (n - 2) × ... × (n - m + 1)
整理一下即：
A(m, n) = n! / (n - m)!

組合

同樣是n個(gè)標(biāo)記不同數(shù)字的小球放入一個(gè)袋子中，也是抽取m個(gè)，但是此時(shí)不算抽取的順序。也就是把排列的結(jié)果n!/(n - m)!再除以m個(gè)小球隨機(jī)排列的總方法術(shù)，即m!，所以結(jié)果為：

C(m, n) = A(m, n) / m! = n! / ( (n - m)! × m! )

如何得出之前的公式

運(yùn)用以上的知識(shí)，可以總結(jié)出以下公式：

C(m, n + m) = A(m, n + m) / m!

            = (n + m)! / ( n! × m! )