有關(guān)排列組合的一道算法題
一址遇、題目內(nèi)容
廢話不多說，先上題目：
有一個 n × m 的網(wǎng)格滋戳，左下角為A钻蔑，右上角為B，規(guī)定每次只能走一步奸鸯，并且方向只能是向上或者向右咪笑，求A到B共有多少種走法？(例如一個日字形的格子就是一個2 × 1的網(wǎng)格娄涩，共有3種走法)并用Javascript寫出程序算法窗怒。
大家可以先思考一下怎么做，再去看我的方法钝满。
二兜粘、解決方法
這個問題我想了很久，一直在走彎路弯蚜，其實用一個抽象的數(shù)學(xué)方法就可以很輕松解決這個問題。
現(xiàn)在你可以把向右移動想象成記錄一個數(shù)字1剃法，把向上移動抽象成記錄一個數(shù)字0碎捺，并且這些數(shù)字是按順序排列的。
看到這里我相信聰明的小伙伴已經(jīng)想到了如何解決這個問題贷洲。
這個問題可以抽象成n個0和m個1的不同排列的總數(shù)收厨。比如2 × 2的網(wǎng)格就是2個0和2個1的所有不同排列的數(shù)量，也就是1100优构，1010诵叁，1001，0110钦椭，0101拧额，0011碑诉。
進而，我們可以把問題抽象成從(m + n)個0中侥锦，隨意抽取m個0并將它改為1的不同方法數(shù)进栽，是不是覺得問題很熟悉，沒錯恭垦！就是高中的排列組合快毛。我先把公式亮出來??：
C(m, n + m) = (n + m)!/(m! * n!)
想先復(fù)習(xí)一下排列組合知識的同學(xué)可以參見下一節(jié)。
三番挺、Javascript代碼描述
以上的結(jié)果用JS的描述唠帝，如下：
function getMethods(n, m) {
// 定義一個求階乘的輔助函數(shù)
function factorial(x) {
if (x === 0) {
return 1
} else {
return factorial(x -1) * x
}
}
return factorial(m + n)/(factorial(m) * factorial(n))
}
如果小伙伴有好的算法，可以留言交流玄柏！
四襟衰、排列組合
簡單地講一下排列和組合。
排列
先舉個栗子（以下n禁荸，m均為正整數(shù)）右蒲，從n個含有標有不同數(shù)字小球的袋子里，按順序抽取n個小球赶熟，且抽取后不再放入袋子里瑰妄。第一次抽的時候，有n種可能映砖；第二次抽的時候有n - 1種可能间坐，以此類推，抽完n個小球總共的不同排列個數(shù)為n!邑退。
如果條件不變竹宋，只把抽取的小球個數(shù)改為m（m <= n）個，結(jié)果也就變成：
n × (n - 1) × (n - 2) × ... × (n - m + 1)
整理一下即：
A(m, n) = n! / (n - m)!
組合
同樣是n個標記不同數(shù)字的小球放入一個袋子中地技，也是抽取m個蜈七，但是此時不算抽取的順序。也就是把排列的結(jié)果n!/(n - m)!再除以m個小球隨機排列的總方法術(shù)莫矗，即m!飒硅，所以結(jié)果為：
C(m, n) = A(m, n) / m! = n! / ( (n - m)! × m! )
如何得出之前的公式
運用以上的知識，可以總結(jié)出以下公式：
C(m, n + m) = A(m, n + m) / m!
= (n + m)! / ( n! × m! )
