一、什麼是動態規劃？
動態規劃就是通過採用分而治之的策略，通過解決大問題的子問題從而解決整體的做法。動態規劃的核心思想就是將大問題拆分成多個子問題，按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
動態規劃有三個重要的概念
1）最優子結構
2）邊界
3）狀態轉移公式
二、動態規劃應用
單看定義的話可能有些抽象，現在我舉個動態規劃實際應用的簡單例子，也是面試中經常出現的問題-上臺階問題。
1）上臺階問題
如果有一座高度為十的臺階，每步只能向上一層或者兩層，請問一共有多少種走法？（比如可以每次都上一層，那走法就是1，1，1，1，1，1，1，1，1，1，也可以每次上兩層，那走法就是2，2，2，2，2）
如果不瞭解動態規劃的話，可能直接選擇排列組合的方式，通過遍歷所有可能來獲取結果。但是這種方法無論是時間複雜度還是空間複雜度都是相當的高。
現在我們可以用動態規劃的思想來看下如何解決這道問題
首先我們把大問題儘量拆分成子問題，如果還有一步就能到達第十層臺階，會有幾種走法？
答案是兩種，一種是當前在第九層臺階，下一步只需要上一層就可以達到終點。另一種是當前在第八層臺階上，下一步只需要上兩層就可以達到終點。
如果到達第八層的所有走法為F（8），到達第九層的所有走法為F（9），那麼到達第十層的所有做法是否就是F（10）？
因此我們可以知道F（10）=F（8）+F（9），這樣我們就完成了第一個字問題的拆分！（最優子結構）
同理可知F（9）=F（7）+F（8），F（8）=F（6）+F（7）。。。。。F（3）=F（1）+F（2）
可以得出F（n）=F（n-1）+F（n-2）（狀態轉移公式）
F（1）和F（2）的值我們可以直接得出結果，分別是1和2，這種無需簡化直接可以得到結果的子問題，我們稱之為邊界。（如果問題沒有邊界的話，我們將永遠無法得到最終結果！）
我們可以根據以上結果得出以下一段代碼！
<code>public int countClimbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int prePreCount = 1;
int preCount = 2;
int count = 0;
for (int i = 3; i <= n; i++) {
count = prePreCount + preCount;
prePreCount = preCount;
preCount = count;
}
return count;
}
/<code>
2）路徑問題
一個矩陣map中每個格子有一個值。從左上角的格子開始每次只能向右或者向下走，最後到達右下角的位置，修改所有的路徑中最小的路徑和。
按照動態規劃的思路可以將這個問題拆分，走到x，y的最小路徑就是S[x][y]=map[x][y]+min(S[x-1][y]（x>0）, S[x][y-1](y>0))（狀態轉移公式）
第一行就只能一直向右和第一列只能一直向下，這個就是邊界。
我們可以根據以上結果得出以下一段代碼！
<code>public int getMinRoute(int[][] map, int x, int y) {
int[][] route = new int[x][y];
int xSum = 0;
//邊界賦值
for (int i = 0; i < x; i++) {
for (int j = 0; j <= i; j++) {
route[i][0] += map[j][0];
}
}
for (int i = 0; i < y; i++) {
for (int j = 0; j <= i; j++) {
route[0][i] += map[0][j];
}
}
for (int i = 1; i < x; i++) {
for (int j = 1; j < y; j++) {
route[i][j] = map[i][j] + Math.min(route[i][j - 1], route[i - 1][j]);
}
}
return route[x - 1][y - 1];
}/<code> 3）揹包問題
在N件物品取出若干件放在容量為V的揹包裡，求揹包能夠容納的最大價值。
按照同樣的思路分析問題，我們可以選擇拿和不拿兩種，那麼我們需要判斷這兩種情況哪種收益大，取最大值。
重量weight[n]，價值value[n]
F（N，V）=max（F（N- 1, V - weight[i]）+value[i], F（N - 1, V））
<code>public static int maxValue(int[] weight, int[] value, int N, int V) {
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i < N + 1; i++) {
for (int j = 1; j < V + 1; j++) {
if (weight[i - 1] > j) {// 可能存在裝不下的情況
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
}
}
}
return dp[N][V];
}/<code>
閱讀更多 加班狗的微博 的文章
