簡單動態規劃—爬樓梯
- 2020 年 3 月 18 日
- 筆記
又到了每周的演算法時間了，今天給大家帶來一道很經典，又很簡單，又比較適合對動態規劃極度恐懼的童鞋，做動態規劃的題，一定要學會分析，慢慢找到狀態轉移方程，不多說，來看看題目：
題目
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數。
示例 1：
輸入：2 輸出：2 解釋： 有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階
示例 2：
輸入：3 輸出：3 解釋： 有三種方法可以爬到樓頂。 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階
解題思路
這道題目算得上最簡單的動態規劃類的題目了，我們來一個一個分析一下：
- 當只有 1 階台階時，你只有一種方式爬到頂端
- 當只有 2 階台階時，你有兩種方式，如示例1所示
- 當只有 3 階台階時，你有三種方式，如示例2所示
分析到這裡的時候，看看這幾個數據，我有一個大膽的猜測，當只有 4 階台階時，可以有 爬到第2階台階所需要的方法數 加上 爬到第3階台階所需要的方法數 種方法數，為什麼這麼說呢？你想想，要想爬到第4階台階，你只能是從第3階或者第2階台階爬上來的，只有這兩種方式對吧，所以：
4階方法總數 = 3階方法總數 + 2階方法總數
題解
public static int climbStairs(int n) { if (n == 1) { return 1; } if (n == 2) { return 2; } int[] steps = new int[n]; steps[0] = 1; steps[1] = 2; for (int i = 2; i < n; i++) { steps[i] = steps[i - 1] + steps[i - 2]; } return steps[n - 1]; }
