【劍指Offer】跳臺階
題目描述
一隻青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法(先後次序不同算不同的結果)。
解法1
首先對這道題,我們可以通過找規律來解
一隻青蛙可以跳上1級臺階,也可以跳上2兩級臺階
當n = 1時,有1種跳法
當n = 2時,有2種跳法
當n = 3時,有3種跳法
當n = 4時,有5種跳法
當n = 5時,有8種跳法
...
等等,1,2,3,5,8...,多麼熟悉的數列,斐波那契?
仔細想想當有n(n >= 2)級臺階時,求F(n)
青蛙第一步可以選擇跳上1級臺階,則還剩n - 1級臺階需要跳,即F(n - 1)
青蛙第一步也可以選擇跳上2級臺階,則還剩n - 2級臺階需要跳,即F(n - 2)
則總的跳法F(n) = F(n - 1) + F(n - 2),毫無疑問這就是斐波那契數列的定義了。
關於斐波那契的求解方法,讀者可以參考【劍指Offer】斐波那契數列 ,包括了遞迴,動態規範,矩陣快速冪多種解法,這裡就不再贅述了。
下面放上以求解斐波那契數列的方式解題的其中一種寫法。
實現程式碼
public int jumpFloor(int number) { int f1 = 0; int f2 = 1; while (number-- > 0) { f2 = f1 + f2; f1 = f2 - f1; } return f2; }
排列組合
網上大多數的解法都是以求解斐波那契數列的思路來解題,但其實使用排列組合的思想也可以求解(真相是一開始沒發現是斐波那契,才想到排列組合的-_-||)。
解題前先簡單介紹下排列組合,摘自百度百科
-
排列的定義:從n個不同元素中,任取m(m≤n,m與n均為自然數,下同)個元素按照一定的順序排成一列,叫做從n個不同元素中取出m個元素的一個
排列
。從n個不同元素中取出m個元素的所有排列的個數,叫做從n個不同元素中取出m個元素的排列數,用符號A(n,m)表示。
\[A{^m_n} =n * (n - 1) * (n-2) * ... *(n-m+1)= \frac{n * (n - 1) * (n - 2) * (n - m + 1) * (n - m)*...* 2 * 1}{(n - m) * (n - m - 1) * (n - m - 2) * ... * 2 * 1} \]
\[A{^m_n} = \frac{n!}{(n - m)!}\]
其中n!表示n的階乘,比如4! = 4 * 3 * 2 * 1
對於\[A{^m_n} =n * (n - 1) * (n-2) * ... *(n-m+1)\] 可以這樣理解,當從n個元素中取第一個元素時,有n種取法。當再取第2個元素時,此時還剩n - 1個元素,有n - 1種取法。當再取第3個元素時,此時還剩n - 2個元素,有n - 2種取法。以此類推,當取到第m個元素時,此時還剩n - m + 1個元素,有n - m + 1種取法。則總取法為\[n * (n - 1) * (n-2) * ... * (n-m+1)\] -
組合的定義:從n個不同元素中,任取m(m≤n)個元素併成一組,叫做從n個不同元素中取出m個元素的一個
組合
。從n個不同元素中取出m個元素的所有組合的個數,叫做從n個不同元素中取出m個元素的組合數。用符號C(n,m) 表示。
\[C{^m_n} =\frac{A{^m_n}}{m!} = \frac{n!}{(n - m)!m!}\]
排列和組合的區別可以先簡單理解為,從n個不同元素中,任取m個元素,有多少種取法,如果這m個元素的先後順序不同,就認為是不同的取法的話,那麼總取法數就是排列數A(n,m)。如果取出來的m個元素無論先後順序如何,都認為是同一種取法,那麼總取法數就是組合數C(n,m)。舉個栗子,在{1,2,3,4,5}中任取三個數{2, 4, 5}或者{5,2,4},對於排列數來說,它們屬於2種取法,而對於組合數來說它們只算1種取法。
可以發現,排列和組合的區別在於取出來的這m個元素是否有順序性。當有順序性時,這m個元素有A(m,m)種排列順序,所以排列數A(n,m)除以A(m,m),去除m個元素順序性的影響,得到的就是組合數C(n,m),即
\[C{^m_n} =\frac{A{^m_n}}{A{^m_m}}=\frac{A{^m_n}}{m!} \]
解法2
回到本題,青蛙可以跳上1級臺階,也可以跳上2級臺階,
對於n級臺階來說,它最多可以跳 n/2 次 2 級臺階,也就是說總的跳法數是跳0次2級臺階跳法數,1次2級臺階跳法數,2次2級臺階跳法數 ... n/2 次2級臺階跳法數的總和
現在問題就變成了求跳指定次數2級臺階的跳法數
假設有n級臺階,指定要跳m次2級臺階,還剩下n - 2m個1級臺階,則青蛙一共要跳n - 2m + m = n - m次才能跳完。即在n-m次跳躍中選擇m次跳2級臺階,有多少種跳法數呢,C(n - m,m)種。(注意這裡不是An - m,m),因為選出的m次2級臺階沒有順序性)
所以我們求出C(n - 1,1),C(n - 2,2),C(n - 3,3) .. C(n - n/2, n/2),然後將其相加,記得再加上1(選0個2級臺階,1種跳法),就是總的跳法數
實現程式碼時注意求組合數C(n,m)的演算法,需要做一些優化,主要有兩點
先化簡公式
\[C{^m_n} =\frac{A{^m_n}}{m!}=\frac{n * (n - 1) * (n-2) * ... *(n-m+1)}{m!} \]
1,如果C(n,m)的結果用c#的int型別儲存,則最大值為2^31^-1,如果按照公式依次計算分子和分母,可能分子或分母會超過2^31^-1,從而造成異常。所以優化為分子和分母的計算同步進行,當判斷分子除以分母可以除整的時候,就先相除,避免累計數過大。後面的程式碼會有對應註釋。
2,可以省略的計算就省略
比如求解C(5,4),其中的4 * 3 * 2,分子分母可以直接相約,本來分子分母的計算都需要連乘4次,現在只需要連乘1次
\[C{^4_5} = \frac{5 * 4 * 3 * 2}{4 * 3 * 2 * 1} \]
實現程式碼
// 求解cnm public int c(int n, int m) { int count = m; int nf = 1, mf = 1; if (m >= n - m + 1) { // 對應優化2,只需要連乘n-m次 count = n - m; } for (int i =0; i < count; i++) { nf *= (n - i); mf *= (i + 1); // 對應優化1,可以除整的時候就先除 if (nf % mf == 0) { nf = nf / mf; mf = 1; } } return nf / mf; } public int jumpFloor(int number) { int ret = 1; int count = number / 2; for (int i = 1; i <= count; i++) { ret += c(number - i, i); } return ret; }