【算法】【動态規劃】總結

這裡寫自定義目錄标題

• 一、力扣經典題目
• 二、使用循環而非遞歸
• 三、滾動數組思想減少空間占用

一、力扣經典題目

• 509.斐波那契數列
• 1137. 第 N 個泰波那契數
• 70. 爬樓梯

二、使用循環而非遞歸

歸納出動态規劃轉移方程後，可以建立一個n+1的動态規劃數組dp，然後使用循環從前往後或者從後往前進行指派，傳回最後計算出來的數字。

一般簡單地使用遞歸都會産生"超出時間限制"的錯誤。

三、滾動數組思想減少空間占用

對于此類簡單的動态規劃題目，一般都有固定的動态規劃轉移方程，比如：

斐波那契數列和爬樓梯的方程為：

f(x)=f(x−1)+f(x−2)

泰波那契數方程為：

T(n)=T(n−1)+T(n−2)+T(n−3)

兩者都沒有本質上的差別，隻不過是加數的數量不同而已。

這樣的動态規劃問題從簡單的思想出發，都可以使用遞歸的方法來解決，但是這樣做往往會造成超出時間限制或者超出空間限制的問題。

滾動數組思想就是将遞歸這一方法放在了循環裡來進行。

這裡舉例說明斐波那契數列。

斐波那契數列，通常用 F(n) 表示，形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，後面的每一項數字都是前面兩項數字的和。

F(0) = 0，F(1) = 1

F(n) = F(n - 1) + F(n - 2)，其中 n > 1

可以定義a、b、c三個變量來作為存儲方程中兩個加數和一個和的容器，循環往複a=b, b=c, c=a+b。

也即以下代碼。

public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int a = 0, b = 0, c = 1;
        for (int i = 2; i <= n; ++i) {
            a = b; 
            b = c; 
            c = a + b;
        }
        return c;
    }
           

其中，初始定義的a的值并不關鍵，關鍵是b和c的值，分别為 b=F(0)=0， c=F(1)=1，如何定義還是要看a，b，c的指派順序。

如果把 c = a + b 放在循環體的開頭，那麼初始定義的變量值的含義為 a=F(0)=0， b=F(1)=1，c的初始值便沒有任何意義。