爬一個階梯。到頂端總共需走n階，每次你都可以選擇爬1階或2階，問有幾種不同的方法可以爬到階梯頂端?
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.
Example 1:
Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps
Example 2:
Input: 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
解題思路:
以下列出可能性組合
Input: 1
Output: 1
1
Input: 2
Output: 2
1 1
2
Input: 3
Output: 3
1 1 1
1 2
2 1
Input: 4
Output: 5
1 1 1 1
1 2 1
1 1 2
2 1 1
2 2
Input: 5
Output: 8
1 1 1 1 1
1 2 1 1
1 1 2 1
1 1 1 2
1 2 2
2 1 1 1
2 2 1
2 1 2
Input: 6
Output: 13
1 1 1 1 1 1
1 2 1 1 1
1 1 2 1 1
1 1 1 2 1
1 1 1 1 2
1 2 2 1
1 1 2 2
1 2 1 2
2 1 1 1 1
2 2 1 1
2 2 2
2 1 2 1
2 1 1 2
我們考慮要爬n階的話，首先要先爬到n-1階或n-2階，因為只有一次走1階或一次走2階的選擇。也就是說，走到n階的方法，就相當於走到n-1階的方法和走到n-2階的方法和。
n: 階層數
n = 1， result = 1
n = 2, result = 1+1 (爬1階兩次 + 一次爬兩階)
n = 3, result = 1+2 (前面兩個case相加)
n = 4, result = 3+2 (前面兩個case相加)
所有這題可以使用費氏數列來計算結果
using System;
namespace LeetCode_70._Climbing_Stairs
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(ClimbStairs(4));
}
public static int ClimbStairs(int n)
{
if (n <= 2) return n;
int[] arr = new int[n];
arr[0] = 1; arr[1] = 2;
for (int i = 3; i <= n; i++)
{
arr[i - 1] = arr[i - 2] + arr[i - 3];
}
return arr[n - 1];
}
}
}
時間/空間複雜度: O(N)
Ref: