動態規劃是IT技術面試中最難的算法，很多人披荊斬棘，最終還是跪在動態規劃題目上。
今天給大家總結動態規劃十問十答，快速幫你掃盲動態規劃。
答：動態規劃是一種通過「大而化小」的思路解決問題的算法。區別於一些固定形式的算法，如二分法，寬度優先搜索法，動態規劃沒有實際的步驟來規定第一步做什麼第二步做什麼。所以更加確切的說，動態規劃是一種解決問題的思想。這種思想的本質是，一個規模比較大的問題（假如用2-3個參數可以表示），是通過規模比較小的若干問題的結果來得到的（通過取最大，取最小，或者加起來之類的運算）所以我們經常看到的動態規劃的核心——狀態轉移方程都長成這樣：
* f[i][j] = f[i - 1][j] + f[i][j - 1]
* f[i] = max{f[j] if j < i and …} + 1
* f[i][j] = f[0][j - 1] && judge(1,i) || f[1][j - 1] && judge(2,i) || …
答：多。並且越來越多。隨著CS從業與求職者的增加，並伴隨大家都是「有備而來」的情況下，一般簡單的反轉鍊表之類的題目已經無法再在面試中堅挺了。因此在求職者人數與招聘名額的比例較大的情況下，公司會傾向於出更難的面試問題。而動態規劃就是一種比較具有難度，又比較「好出」的面試問題。相比其他的算法與數據結構知識來說，貪心法分治法太難出題了，搜索算法往往需要耗費求職者過長的程序編寫時間一般也不傾向於出，二叉樹鍊表等問題題目並沒有那麼多，而且求職者也都會著重準備這一塊。因此動態規劃這一類的問題，便越來越多的出現在了面試中。
答：動態規劃一般來說是「高效」的代名詞，因為其解決的問題一般退而求其次的算法只有搜索了。以「數字三角形」一題為例子（http://www.lintcode.com/problem/triangle/ ），在「三角矩陣」中找一條從上到下的路徑，使得權值之和最小。如果使用暴力搜索的算法，那麼需求窮舉出2^(n-1)條路徑（n為三角形高度），而使用動態規劃的話，則時間複雜度降低到了n^2，完成了質的飛躍。那麼究竟為什麼這麼快呢？原因在於動態規划算法去掉了「無用和重複的運算」。在搜索算法中，假如從A->B有2條路徑，一條代價為10，另外一條代價為100，B->終點有1024條路徑。當我們選擇了代價為10的那條路徑走到B時，可以繼續往下走完1024條路逕到終點，但是在此之後，我們再從代價為100的路徑從A走到B時，我們可以發現此時無論如何走，都不可能有剛才從10的路徑走過來更好，所以這些計算是「無用」的計算，也可以說是「重複」的計算。這就是動態規劃之所以「快」的重要原因。
答：我們將動態規劃的常見類型分為如下幾種：
* 矩陣型
* 序列型
* 雙序列型
* 劃分型
* 區間型
* 背包型
* 狀態壓縮型
* 樹型
其中，在技術面試中經常出現的是矩陣型，序列型和雙序列型。劃分型，區間型和背包型偶爾出現。狀態壓縮和樹型基本不會出現（一般在算法競賽中才會出現）。
每種類型都有著自己的題目特點和狀態的表示方法。以矩陣型動態規劃為例，一般題目會給你一個矩陣，告訴你有一個小人在上面走動，每次只能向右和向下走，然後問你比如有多少種方案從左上走到右下 (http://www.lintcode.com/problem/unique-paths/)。這種類型狀態表示的特點一般是使用坐標作為狀態，如f[i][j]表示走到(i,j)這個位置的時候，一共有多少種方案。狀態的轉移則是考慮是從哪兒走到(i,j)這個坐標的。而序列型的動態規劃，一般是告訴你一個序列；雙序列的動態規劃一般是告訴你兩個字符串或者兩個序列。
將所做過的動態規劃問題按照這些類別進行歸類，分析狀態的表示方法和狀態轉移方程的構造方法在每種類型中的近似之處，會讓你更快的學會動態規劃。
答：可以使用動態規劃的問題一般都有一些特點可以遵循。如題目的問法一般是三種方式：
1. 求最大值/最小值
2. 求可不可行
3. 求方案總數
如果你碰到一個問題，是問你這三個問題之一的，那麼有90%的概率是使用動態規劃來求解。
要重點說明的是，如果一個問題讓你求出「所有的」方案和結果，則肯定不是使用動態規劃。
答：首先根據「問5」判斷是否是動態規劃的問題，如果是，則嘗試將其按照「問4」進行分類，找到對應的類別和相似的問題。接著從下面的4個要素去逐步剖析解決這道題：
1. 狀態是什麼
2. 狀態轉移方程是什麼
3. 狀態的初始值是什麼
4. 問題要求的最後答案是什麼
每個步驟分析完成之後，就基本上解決了整道動態規劃的問題。
答：一般來說，使用動態規劃求解的問題，時間上已經比暴力搜索要優化很多了。但是仍然存在著一些可以優化的空間。通常來說，動態規劃的時間優化，有如下兩種常見的方式：
1. 通過變換狀態優化
2. 通過決策單調優化
對於通過變換狀態來優化的問題比較難，需要一些經驗和靈感。而對於決策單調的優化，則比較簡單，但適用範圍不廣，一般只適用於劃分型動態規劃當中，通常這個方法可以將複雜度降低一個數量級。
答：動態規劃的空間優化只有一種方法，就是使用滾動數組進行優化。以一個二維的動態規劃為例子。假如狀態轉移方程如下：f[i][j] = f[i - 1][j] + f[i][j - 1]。我們可以發現，第i層的狀態，已經和第i-2層的狀態沒有關係了，那麼這種情況下，用於存儲第i-2層的空間就可以被重複利用。方法非常簡單，把數組的第一維對2取模就可以了：f[i % 2][j] = f[(i - 1) % 2][j] + f[i % 2][j-1]。這種方法通常可以將空間複雜度降低一個數量級。
在 LintCode 上包含了80餘道動態規劃的練習題：
http://www.lintcode.com/tag/dynamic-programming/
都是從實際的面試問題中匯總的精選練習，熟練掌握這些練習題，基本上可以滿足面試需求。
https://www.kancloud.cn/kancloud/pack/70125
PS. 也可以直接在網上搜索背包九講
全網唯一的 DP 專題課程
主講人為：清華大學畢業，全國算法競賽金牌得主，矽谷知名IT企業工程師
免費試聽內容：
動態規劃和遞歸的區別
動態規劃的解題方法歸納
常見動態規劃類型總結
免費試聽時間：
美西時間 4月30日周二 19:00
美東時間 4月30日周二 22:00
北京時間 5月1日周三 10:00
長按二維碼免費試聽：
或點擊文末「閱讀原文」
題目名稱
類型
難度
Word Break
一維
簡單
Maximum Product Subarray
一維
簡單
Longest Increasing Continuous Subsequence
一維
簡單
Perfect Squares
一維
簡單
Decode Ways
一維
簡單
Best Time to Buy and Sell Stock
一維
簡單
Palindrome Partitioning II
一維
中等
House Robber
一維
中等
House Robber II
一維
中等
Decode Ways
一維
中等
Best Time to Buy and Sell Stock III
一維
中等
Longest Increasing Subsequence
一維
難
Best Time to Buy and Sell Stock IV
一維
難
Coins in a Line
一維+博弈
簡單
Coins in a Line II
一維+博弈
中等
Longest Common Subsequence
二維
簡單
Triangle
二維
簡單
Minimum Path Sum
二維
簡單
Minimum Adjustment Cost
二維
中等
Edit Distance
二維
中等
Maximal Square
二維
中等
Maximum Subarray III
二維
難
k sum
二維
難
Maximal Rectangle
二維
難
Paint Fence
二維（一維+狀態）
中等
Paint House
二維（一維+狀態）
中等
Paint House II
二維（一維+狀態）
中等
Interleaving String
二維+字符串
中等
Regular Expression Matching
二維+字符串
難
Wildcard Matching
二維+字符串
難
Copy Books
劃分
中等
Burst Balloons
區間
難
Scramble String
區間+字符串
難
Unique Binary Search Trees II
樹形+計數
簡單
Unique Binary Search Trees
樹形+計數
簡單
Binary Tree Maximum Path Sum
樹形
中等
Backpack
背包
簡單
Backpack II
背包
中等
Dices Sum
背包
中等
Climbing Stairs
計數+一維
簡單
Unique Paths
計數+二維
簡單
Unique Paths II
計數+二維
簡單
Distinct Subsequences
計數+二維
中等
Backpack VI
計數+背包
中等