### LeetCode: 70. Climbing Stairs

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， 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];
}

}
}

Ref: