主題

[LeetCode C#] 70. Climbing Stairs - Recursion With Memoization

帥氣跳蚤蛋 | 2021-07-15 23:10:02 | 巴幣 0 | 人氣 96

難度: 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];
    }

創作回應

相關創作

更多創作