【LeetCode | 動态規劃 1】509. 斐波那契數

寫在前面

講一下開展動态規劃專欄的原因：

1.今天每日一題自閉了 576. 出界的路徑數。

2.從我第一次用LeetCode的明顯體驗出發：

你會看見評論區出現的各種代碼解法前面有DFS+剪枝balabala等算法标簽，

然後會看見一個詞叫DP，一直覺得深奧，看了就覺得自己不會那種，

後來知道原來叫動态規劃 Dynamic Programming

3.直接上難度相當于讓我一步跨五級台階，太難而且容易喪失熱情。

我選擇了LeetCode自帶的學習計劃，并且開始從零起步之旅~

基礎解法

題目都很熟，不贅述，再不濟直接去LeetCode搜一下。

第一本能敲出來的代碼👇

class Solution {
    public int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        return fib(n-1) + fib(n-2); 
    }
}
           

一看用時弱爆了

進階解法

class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
}
           

心得體會

• 基礎解法-遞歸：

  邏輯簡單，容易想到。

• 進階解法-動态規劃：

  複用了上一次的結果。

參考官方題解的動圖食用。

https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/