LeetCode 75 Level 1 - Day 10 Dynamic Programming

70. Climbing Stairs

• 題目連結
• 難易度：Easy

題目敘述

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

預設函數

int climbStairs(int n){

}

題目限制

• 1 <= n <= 45

解題過程及程式碼

本題是 Dynamic Programming的第二題，你正在爬樓梯，需要踏n階才可以到達頂部，但是你每一步都可以選擇一次要踏一階或是一次踏二階，最後要求出踏到n階有幾種不同的踏法，例如：

• n=1時只有1種踏法。
• n=2時就有一次踏一階共踏2次和一次踏二階共踏1次，合計有2種不同的踏法。
• 可以依此類推下去。

想法和[509. Fibonacci Number]很像，若是有4階，因為每步是1-2階，所以4階的踏法可以分成 (最後一步踏二階) + (最後一步踏一階)

• (最後一步踏二階) -> (還剩下2階) -> (就是求2階的踏法)。
• (最後一步踏一階) -> (還剩下3階) -> (就是求3階的踏法)。
• 所以 (4階的踏法) = (3階踏法) + (2階踏法) = 3 + 2 = 5。
• 

第一次用遞迴程式碼上傳

int climbStairs(int n){
    if (n == 0 || n == 1)
        return 1;
    else
        return climbStairs(n-1) + climbStairs(n-2);
}

• 但是這個方法在n=42會Time Limit Exceeded，表示所花費的時間太多。

再修正算法，使用陣列方法，不會Time Limit Exceeded

• 程式碼

int climbStairs(int n){
    int f[46];

    f[0] = 1;
    f[1] = 1;

    for (int i=2; i<=n; i++) {
        f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

今天就到這裡，謝謝大家!