今天簡單說一下動態規劃的定義以及簡單範例。動態規劃，是一種將原問題分解成簡單的子問題來解決複雜問題的思想。
其中，動態規劃還具有最優子結構性質和子問題重疊性質。
最優子結構：動態規劃將原問題分解成各種簡單的子問題時，各個子問題的最優解綜合起來就是原問題的最優解，即區域性最優解能夠決定全域性最優解。
子問題重疊：在計算一個子問題的最優解之後，記住這個子問題，接下來還可能遇到相同問題，為提高效率，可以直接拿來之前得到的結果，這是因為當使用遞迴自頂向下的時候，每次產生的子問題不總是新問題，而是之前被重複計算的問題。
接下來簡單利用斐波那契數列來介紹一下動態規劃：
斐波那契數列：0，1，1，2，3，5，8，13，21，34，55，89、、、、、、規律是從第三項開始，每一項都等於前兩項之和，F(n)=F(n-1)+F(n-2),(n>=3)
問題簡單描述：
給一個整型數值n，輸出斐波那契數列中對應的第n項數值
在不瞭解動態規劃地情況下，我們一般都是利用普通遞回來解決
1 public int fabocci(int n){ 2 if(n<1) 3 return 0; 4 else if(n==1) 5 return 1; 6 else if(n==2) 7 return 1; 8 return fabocci(n-1)+fabocci(n-2); 9 }
顯然每次呼叫fabocci函數時，因為第三項之後都是前兩項之和，所以會出現大量的重複計算，且時間複雜度為O(2^n)
基於相鄰兩項之和可以推出下一項，於是可以採用自底向上的方法：
1 public int fabocci(int n){ 2 if(n<1) 3 return 0; 4 else if(n==1) 5 return 1; 6 else if(n==2) 7 return 1; 8 //temp1,temp2既是相鄰兩項的值，也是為了記錄迭代出來的結果，方便下一次計算使用 9 int temp1=1; 10 int temp2=1; 11 int temp=0; 12 for(int i=3;i<=n;i++){ 13 temp=temp1+temp2; 14 temp1=temp2; 15 temp2=temp; 16 } 17 return temp; 18 }
以上僅以學習記錄，如有問題，請及時指正，我們共同進步，謝謝！