動态規劃和遞推有些相似（尤其是線性動規），但是不同于遞推的是：
遞推求出的是資料，是以隻是針對資料進行操作；而動态規劃求出的是最優狀态，是以必然也是針對狀态的操作，而狀态自然可以出現在最優解中，也可以不出現——這便是決策的特性（布爾性）。其次，由于每個狀态均可以由之前的狀态演變形成，是以動态規劃有可推導性，但同時，動态規劃也有無後效性，即每個目前狀态會且僅會決策出下一狀态，而不直接對未來的所有狀态負責，可以淺顯的了解為——Future never has to do with past time ,but present does.
現在決定未來，未來與過去無關。
動态規劃常常适用于有重疊子問題和最優子結構性質的問題，動态規劃方法所耗時間往往遠少于樸素解法。
動态規劃背後的基本思想非常簡單。大緻上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。
通常許多子問題非常相似，為此動态規劃法試圖僅僅解決每個子問題一次，進而減少計算量：一旦某個給定子問題的解已經算出，則将其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關于輸入的規模呈指數增長時特别有用。
動态規劃适用的場景：
1.最優子結構
最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動态規劃算法解決問題提供了重要線索。
2.無後效性
無後效性。即子問題的解一旦确定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。
3.子問題重疊
子問題重疊性質。子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次産生的子問題并不總是新問題，有些子問題會被重複計算多次。動态規劃算法正是利用了這種子問題的重疊性質，對每一個子問題隻計算一次，然後将其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，隻是在表格中簡單地檢視一下結果，進而獲得較高的效率。
所熟知的斐波那契數列的遞推式就是動态規劃的一種展現
f(i)=f(i−1)+f(i−2),i>=3f(i)=f(i−1)+f(i−2),i>=3
從遞歸搜尋的角度去思考斐波那契數列
int f(int n) { if(n == 1 || n == 2)return 1; else return f(n - 1) + f(n - 2); }
我們會發現上面的程式在超過50項之後計算速度就會以肉眼可見的速度下降，原因是什麼呢，就是因為該程式在計算的過程中遇到了大量的子問題的重疊計算。
在計算斐波那契的過程中出現了大量的子問題重疊過程
解決方法1
記憶化
const int N = 10000;
long long f[N];
long long foi(int n)
{
if(f[n] != 0)return f[n];
if(n == 1 || n == 2)return 1;
else return f[n] = foi(n-1) + foi(n-2);
}
此時你會發現我們用記憶化搜尋就可以解決這個問題，為什麼還要用動态規劃呢，我們會發現我們使用搜尋來擷取結果是從自頂向下的思考方式去尋找答案。那麼我們動态規劃又是如何解決問題的呢
解決方案2
動态規劃
void dp()
f[1] = 1;f[2] = 1;
for(int i = 3;i <= n ;i ++)
f[i] = f[i-1] + f[i-2];
此時我們發現根據狀态轉移方程我們的計算過程是從 1 - n 而我們的記憶化搜尋是從 n - > 1 --> n 也就是說這裡的動态規劃是從自底向上解決問題(當然dp問題不一定都可以用搜尋樹的形式表示，即: 不是所有的動态規劃都可以轉化為記憶化搜尋問題，而所有的記憶化搜尋問題一定可以找到一個狀态裝一方城轉化成動态規劃)
動态規劃解決問題的步驟
綜上我們大緻可以總結出解決動态規劃問題的一般步驟
1. 尋找最優子結構(狀态表示)
2. 歸納狀态轉移方程(狀态計算)
3. 邊界初始化
數字三角形 Number Triangles
首先我們從搜尋的角度去分析問題
加上記憶化優化
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 10005;
int a[N][N] , f[N][N],n;
int dfs(int x , int y)
if(f[x][y] != 0)return f[x][y];
if(x == n)return a[x][y];
int sum = max(dfs(x + 1,y),dfs(x + 1,y + 1));
return f[x][y] = sum + a[x][y];
}
int main()
cin >> n;
for(int i = 1;i <= n ;i ++)
{
for(int j = 1;j <= i;j ++)
{
scanf("%d",&a[i][j]);
}
}
dfs(1 , 1);
cout << f[1][1] << endl;
動态規劃解法
const int N = 505;
const int INF = 2e9;
int a[N][N] , f[N][N] , n ;
int ans = 0;
// 從上往下推
for(int i = 0;i <= n ;i ++)
for(int j = 0;j <= i + 1;j ++)
f[i][j] = -INF;
f[1][1] = a[1][1];
for(int i = 2;i <= n ;i ++)
f[i][j] = max(f[i-1][j-1],f[i-1][j]) + a[i][j];
for(int i = 1;i <= n ;i ++)ans = max(ans,f[n][i]);
//從下往上推
void dp2()
for(int i = n ;i >= 1;i --)
for(int j = i;j >= 1 ;j --)
f[i][j] += max(f[i+1][j],f[i+1][j+1]) + a[i][j];
}
for(int j = 1;j <= i ;j ++)
dp();cout << ans << endl;
return 0;