主題
難度: Easy
===========================================================================
說明:
你在爬樓梯,需要n步才能登頂.
一次可走1步或2步,可以使用多少種走法達到頂部?
===========================================================================
測資:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
===========================================================================
條件限制:
1 <= n <= 45
===========================================================================
解題:
此題為Fibonacci數列:
| 階梯數 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 走法(種) | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
此數列的公式為f(n)=f(n-1)+f(n-2)
初始條件:
在第0階與第1階,只有1種走法
f(0)=1
f(1)=1
------------------------------------------------------------------------------------------------------------------------------------
解法1-使用陣列計算:
public int ClimbStairs(int n)
{
int[] num = new int[n + 1];//n=1~45
num[0] = 1;//初始條件
num[1] = 1;//初始條件
for (int i = 2; i <= n; i++)
num[i] = num[i - 1] + num[i - 2];//數列公式
return num[n];
}
------------------------------------------------------------------------------------------------------------------------------------
解法2,遞迴(計算時間過久,Leetcode會timeout):
public int ClimbStairs(int n)
{
if (n <= 1)//初始條件
return 1;
return ClimbStairs(n - 1) + ClimbStairs(n - 2);//數列公式
}
------------------------------------------------------------------------------------------------------------------------------------
解法3,帶有記憶的遞迴,減少重覆計算:
int[] result = new int[46]; //n最大為45所以陣列長度要46
public int ClimbStairs(int n)
{
if (n <= 1)//初始條件
return 1;
if (result[n] > 0)//搜尋陣列,若先前已計算過則返回結果
return result[n];
result[n] = ClimbStairs(n - 1) + ClimbStairs(n - 2);//數列公式
return result[n];
}
達人
