## 跳臺階問題 ### 題目描述 一個臺階總共有n 級，如果一次可以跳1 級，也可以跳2 級。 求總共有多少總跳法，并分析算法的時間復雜度。 ### 分析與解法 #### 解法一 首先考慮最簡單的情況。如果只有1級臺階，那顯然只有一種跳法。如果有2級臺階，那就有兩種跳的方法了：一種是分兩次跳，每次跳1級；另外一種就是一次跳2級。 現在我們再來討論一般情況。我們把n級臺階時的跳法看成是n的函數，記為f(n)。 - 當n>2時，第一次跳的時候就有兩種不同的選擇： - 一是第一次只跳1級，此時跳法數目等于后面剩下的n-1級臺階的跳法數目，即為f(n-1)； - 另外一種選擇是第一次跳2級，此時跳法數目等于后面剩下的n-2級臺階的跳法數目，即為f(n-2)。 因此n級臺階時的不同跳法的總數f(n)=f(n-1)+f(n-2)。 我們把上面的分析用一個公式總結如下： ``` / 1 n = 1 f(n)= 2 n = 2 \ f(n-1) + f(n-2) n > 2 ``` 原來上述問題就是我們平常所熟知的Fibonacci數列問題。可編寫代碼，如下： ```cpp long long Fibonacci(unsigned int n) { int result[3] = {0, 1, 2}; if (n <= 2) return result[n]; return Fibonacci(n - 1) + Fibonacci(n - 2); } ``` 那么，如果一個人上臺階可以一次上1個，2個，或者3個呢？這個時候，公式是這樣寫的： ``` / 1 n = 1 f(n)= 2 n = 2 4 n = 3 //111, 12, 21, 3 \ f(n-1)+f(n-2)+f(n-3) n > 3 ``` #### 解法二 解法一用的遞歸的方法有許多重復計算的工作，事實上，我們可以從后往前推，一步步利用之前計算的結果遞推。 初始化時，dp[0]=dp[1]=1，然后遞推計算即可：dp[n] = dp[n-1] + dp[n-2]。 參考代碼如下： ```c //1, 1, 2, 3, 5, 8, 13, 21.. int ClimbStairs(int n) { int dp[3] = { 1, 1 }; if (n < 2) { return 1; } for (int i = 2; i <= n; i++) { dp[2] = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = dp[2]; } return dp[2]; } ``` ### 舉一反三 1、兔子繁殖問題 13世紀意大利數學家斐波那契在他的《算盤書》中提出這樣一個問題：有人想知道一年內一對兔子可繁殖成多少對，便筑了一道圍墻把一對兔子關在里面。已知一對兔子每一個月可以生一對小兔子，而一對兔子出生后.第三個月開始生小兔子假如一年內沒有發生死亡，則一對兔子一年內能繁殖成多少對？ 分析：這就是斐波那契數列的由來，本節的跳臺階問題便是此問題的變形，只是換了種表述形式。 2、換硬幣問題。 想兌換100元錢，有1,2,5,10四種錢，問總共有多少兌換方法。 ``` const int N = 100; int dimes[] = { 1, 2, 5, 10 }; int arr[N + 1] = { 1 }; for (int i = 0; i < sizeof(dimes) / sizeof(int); ++i) { for (int j = dimes[i]; j <= N; ++j) { arr[j] += arr[j - dimes[i]]; } } ``` 此問題還有一個變形，就是打印出路徑目前只想到要使用遞歸來解決這個問題。對此，利用一個vector來保存路徑，每進入一層，push_back一個路徑，每退出一層，pop_back一個路徑。