【LeetCode】 70. Climbing Stairs

Description

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.

你正在爬樓梯。到頂端總共有n階。
每次你都可以爬1或是2階，請問你總共有幾種不同的方法爬到頂呢？
提醒：n只會是正整數。

Example:

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

Solution

• 最基本的遞迴問題，第n階會是n-1和n-2的加總，答案即為費氏數列。
• 稍微值得注意的點，我們得把已經算過的階梯給記錄起來，用以加速。

Code

class Solution {
public:
    int table[100]={0};
    int Find(int f)
    {
        if(table[f]) return table[f];
        table[f] = Find(f-1)+Find(f-2);
        return table[f];
    }
    int climbStairs(int n) {
        table[1]=1;
        table[2]=2;
        table[3]=3;
        return Find(n);
    }
};

tags: LeetCode C++