AI編輯：我是小將
對很多問題，動態規劃（Dynamic Programming）是個強有力的武器，因為大部分情況下它可以大大降低算法的時間復雜度。動態規劃的一個重要的應用是在滿足最優性原理的優化問題，所謂最優性原理指的是問題的一個最優解總是包含子問題的最優解，但這并不是說所有子問題的最優解都對最終解做貢獻。動態規劃與分治法（Divide-and-Conquer）策略比較類似，都是將一個問題分解成子問題，但是分治法一般用于獨立子問題的情形，就是說子問題之間沒有重疊，而動態規劃對子問題重疊的情形特別有效。如同分治法一樣，動態規劃是一種通用性的方法，所以我們還是從例子出發來深刻理解動態規劃。
斐波那契數列數列大家再熟悉不過了，其滿足以下遞推式：
遞歸式已經給出了，我們很容易使用遞歸的方式來實現計算斐波那契數列第項的值：
// 使用遞歸的方式計算斐波那契數列
int fib(int n)
{
if (n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
代碼是那么的簡潔，但是當你計算的非常大時，你發現計算速度會很慢。為什么呢？我們從函數的實現可以看到，每次計算時，我們其實將其分解成兩個子問題：計算和。然后合并兩個子問題得到原問題的解。仔細一看，這是分治法的思想。但是用到這里就存在了問題，因為兩個子問題可能有交叉，比如你要計算，你需要計算和，但是計算兩者都會需要，所以會有很多子問題被重復計算了。這當然會大大降低效率。說點題外話，分治法的一個典型應用是歸并排序，但是劃分的兩個子數組排序是互不影響的，兩者也沒有任何交集，最后直接合并兩個有序數組就可以了。但是對于斐波那契數列問題，分治法會重復計算一些子問題，這是非常低效的。考慮到這點，我們可以使用一個數組表，保存已經計算過的個子問題的解，一旦遞歸需要子問題，我們首先去表中查找，一旦發現已經計算過，就重復利用這個結果。基于這種思想，我們改進了上面的算法：
// table是大小為n+1的數組，為了利用已經計算的結果
int fib(int n, vector<int>& table)
{
// 重復利用
if (table[n] != 0) return table[n];
// 無，那就要將結果保存至table
if (n <= 2)
{
table[n] = 1;
}
else
{
table[n] = fib(n - 1, table) + fib(n - 2, table);
}
return table[n];
}
利用一個查詢表，我們可以避免很多子問題的重復計算。這就是動態規劃的思想。但是有一點，我們采用了遞歸的方式，這意味著我們在設計方案時，采用的是“自上而下”的方式，這是分治法經常使用的方案：從原問題出發，拆分子問題，繼續......，直到無法拆分。盡管看起來是自上而下，但是其實計算時還是先從小的實例開始。我們不禁會想，既然我們使用利用子問題的解來求解原問題，可不可以先從最小的實例開始，即直接采用“自下而上”的方案。完全沒有問題，其實動態規劃大部分都是采用“自下而上”的思路。這樣做有兩個好處，首先我們避免的代價較高的遞歸，因為可以采用循環的方式。其次，有時候我們可以減少內存的使用，因為可能不必存儲所有子問題，子問題利用后就被丟棄，不會影響會面的計算。基于這種思路，我們給出了最終版本：
int fib(int n)
{
int a = 1, b = 1;
for (int i = 3; i <= n; ++i)
{
int tmp = b;
b += a;
a = tmp;
}
return b;
}
上面我們從最小的實例開始，利用循環的方式來高效地完成整個計算。可以看到動態規劃的思路一般是：（1）確立一種遞歸關系，就是聯系原問題與子問題解之間聯系；（2）首先從最小實例開始，以自下而上的方式求解原問題。有時候，我們需要記錄每個子問題的解，有時候卻并不需要。其實采用“自下而上”的方式是優先考慮的方式，但是這并不代表你不可以采用“自上而下”的方案。
斐波那契數列畢竟過于簡單，這里開始一個復雜一點的例子：最大公共子序列（Longest Common Subsequence，LCS）。其問題是給定兩個序列和，其長度分別為和，求解其最大公共子序列的長度，子序列是指從原序列中任意去掉若干元素（不一定連續）而形成的序列。這個問題的一個應用實例是在基因序列匹配。這里我們假定兩個序列都是字符串。比如：為'ABAZDC'，而為'BACBAD'。那么可以得到其LCS為'ABAD'，其長度為4。要使用動態規劃來解決這個問題，首先我們要構造遞歸關系。假定為序列和的LCS長度，那么我們是否可以使用更小的實例來求解呢？更小的實例是指的是什么？我們不妨將序列減少一個長度，可能的子問題是
可以看到原問題總是可以利用子問題的解，這正好符合動態規劃的原則。我們使用數組保存各個子問題的解，然后采用自下而上的原則，從較小的實例出發，利用遞歸式不斷向前計算，直到求得原問題的解。下面是具體的實現：
int lcs(const string& s, const string& t)
{
// 保存子問題最大公共子序列長度，初始化為0
vector<vector<int>> len(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); ++i)
{
for (int j = 1; j <= t.size(); ++j)
{
if (s[i - 1] == t[j - 1])
{
len[i][j] = len[i - 1][j - 1] + 1;
}
else
{
len[i][j] = max(len[i][j - 1], len[i - 1][j]);
}
}
}
return len[s.size()][t.size()];
}
可以看到上面的算法復雜度為。但是有一點，上面只是計算出了LCS的長度，但是假如你想得到實際的LCS，那么該怎么辦？其實可以從入手，找到LCS。不過這次要從這個矩陣的最右下角的元素開始，我們去比較其與左邊及上邊元素，如果和其中任何一個元素相等，那么任選一個元素移動到那里（如果和兩個元素都相等，說明最大公共子序列可能不止一個）。如果都不相等，那么將其移動到左上角位置，此時對應上面的情形2，并將這個位置的對應的元素輸出。不斷重復這個過程，程序將逆序輸出LCS。具體的實現如下：
string lcs(const string& s, const string& t)
{
// 保存子問題最大公共子序列長度，初始化為0
vector<vector<int>> len(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); ++i)
{
for (int j = 1; j <= t.size(); ++j)
{
if (s[i - 1] == t[j - 1])
{
len[i][j] = len[i - 1][j - 1] + 1;
}
else
{
len[i][j] = max(len[i][j - 1], len[i - 1][j]);
}
}
}
// 計算lcs
string ls = '';
for (int i = s.size(), j = t.size(); i >= 1 && j >= 1; )
{
if (len[i][j] == len[i - 1][j])
{
--i;
}
else if (len[i][j] == len[i][j - 1])
{
--j;
}
else
{
ls += s[i-1];
--i;
--j;
}
}
reverse(ls.begin(), ls.end());
return ls;
}
采用“自下而上”的方式，我們總是從較小的實例開始，然后利用遞歸關系前進。算法是采用循環的方式來完成的。在循環時，一定要確保較小的實例先被計算出來。但是你同樣可以選擇“自上而下”的思維，那就是利用遞歸，因為有了遞歸關系，寫出一個遞歸函數是那么地自然：
// 效率低下的遞歸
int recursionLcs(const string& s, int i, const string& t, int j)
{
// 邊界條件
if (i == 0 || j == 0) return 0;
// 遞歸關系
if (s[i - 1] == t[j - 1])
{
return 1 + recursionLcs(s, i - 1, t, j - 1);
}
return max(recursionLcs(s, i, t, j - 1), recursionLcs(s, i - 1, t, j));
}
int lcs(const string& s, const string& t)
{
return recursionLcs(s, s.size(), t, t.size());
}
是不是很簡單，但是這個效率很低下，時間復雜度是指數級的。因為會造成重復計算，所以還是要建立一個查詢表，一旦較小的實例已經被計算，就放入這個表中，以供下次查詢使用。所以，修改如下：
// 動態規劃
int recursionLcs(const string& s, int i, const string& t, int j, vector<vector<int>>& table)
{
// 先進行查詢 （-1代表沒有計算過）
if (table[i][j] != -1) return table[i][j];
// 邊界條件
if (i == 0 || j == 0) { table[i][j] = 0; }
// 遞歸關系
else if (s[i - 1] == t[j - 1])
{
table[i][j] = 1 + recursionLcs(s, i - 1, t, j - 1, table);
}
else
{
table[i][j] = max(recursionLcs(s, i, t, j - 1, table),
recursionLcs(s, i - 1, t, j, table));
}
return table[i][j];
}
int lcs(const string& s, const string& t)
{
vector<vector<int>> table(s.size() + 1,
vector<int>(t.size() + 1, -1));
return recursionLcs(s, s.size(), t, t.size(), table);
}
我們增加了一個查詢表，從而避免相同子問題的重復計算，這有利于提升效率。這是“自上而下”式的動態規劃，從本質上兩者沒有任何區別。前面說過，我們優先選擇循環式的“自下而上”的設計。其實，這也不盡然。因為“自上而下”的方式有可能更高效。為什么呢？因為遞歸的過程中只會計算真正需要使用的子問題，但是“自下而上”的方式往往需要把所有子問題計算出來，因為大部分時候我們可能并不知道到底哪些子問題是后面計算需要的。孰優孰劣，很難說。看你自己的選擇，不過還是優先推薦“自下而上”的策略。
背包問題估計你不會陌生，因為提到它，就想到了動態規劃。我們先來定義問題：假設有件物品，記為，其中物品的重量為，其價值為，同時假定你的背包的最大容量為。現在讓你做個選擇，如何在保證不超過背包容量的前提下，使挑選的物品的總價值最大。一種最直觀的方式是采用暴力窮舉法，考慮所有的物品組合情況，共有個子集，所以暴力窮舉法具有指數級時間復雜度。這有時候并不太現實。另外一種思路是采用貪婪策略，從最貴重的物品開始，直到背包容量不夠。但是這同樣有問題，因為如果貴重物品的重量與價值比很大，此時這種策略就會失效。考慮到這點，你可以先計算每個物品的單位重量價值，然后按此遞減排序，應用貪婪策略選擇物品。假如有件物品，其重量分別為，對應的價值分別為，背包容量是。按上面的策略，最終選擇的物品為物品1和物品3，總價值為。但是其實最優選擇是物品2和物品3，總價值為。看來貪婪算法要想得到最優解，還是有困難的。
那么我們考慮使用動態規劃來解決背包問題，關鍵是看大問題可以不以利用子問題。假如是的最優子集，我們要想拆分問題，就必須要減少問題的維度，我們把最后一個物品單獨拿出來考慮，那么到底是否含有這個物品？我們可以分情況考慮，假如不含這個物品，那么這個相當于在物品集中尋找最優背包。但是如果含有物品，由于物品的價值已經定了，所以相當于在物品集中尋找最優背包。所以，原問題可以重用兩個子問題的解（取兩種情況最大值）。而且子問題也很清楚了，你需要知道前個物品的最優背包解，但是背包容量到底需要選擇哪些，不清楚，需要根據原問題來推，但是肯定不會超過原有背包的容量。所有我們可以計算所有的情況。這樣，我們不妨記為前個物品的最優背包解，背包容量是。那么，遞推關系為：
上面的遞推式要特別注意容量約束。計算出，就是原問題的解，所以我們需要計算一個二維數組，大小為。所以時間復雜度為。直觀看起來，時間復雜度肯定低于指數級。但是事實上有可能比暴力窮舉法性能還差，考慮到可能遠遠大于，那么誰優誰劣，就很難說了。不過，此時我們先采用“自下而上”的方式求解這個問題，就是采用循環的方式計算一個二維數組：
int knapsack(const vector<int>& w, const vector<int>& p, int W)
{
// 定義二維數組
vector<vector<int>> ops(w.size() + 1, vector<int>(W + 1, 0));
// 利用遞推關系
for (int i = 1; i <= w.size(); ++i)
{
for (int j = 1; j <= W; ++j)
{
if (w[i - 1] <= j)
{
ops[i][j] = max(ops[i - 1][j], p[i - 1] + ops[i - 1][j - w[i - 1]]);
}
else
{
ops[i][j] = ops[i - 1][j];
}
}
}
return ops[w.size()][W];
}
兩層循環，解決問題。但是上面只是計算出了背包最優解的最大價值，但是如果你想求得這個最優解到底包含哪些物品，你可以用與最大公共子序列類似的方法，從這個二維數組最低下開始，逆著前推。這里就不貼代碼了，基本和上面是類似的思路。
“自下而上”的方式講完了，但是就像前面說的，我們必須把所有的子問題都計算出來。但是其實，我們有時候并不需要所有的子例。這里我們以前面的那個例子來從逆向計算，以判斷到底需要計算哪些子問題。我們的原問題是要計算，要計算這個值，我們需要計算以及。繼續推，要計算，我們要計算和。同樣地，要計算，我們需要計算以及。所以我們實際上僅需要計算項，而采用“自下而上”的策略，你需要計算項。可以看到，我們不必要地計算出了很多子項。但是對于“自下而上”策略來說，這是無法避免的，因為你并不知道哪些子問題是原問題所需要的，所以只能采用最盲目的方式。但是我們可以采用“自上而下”的策略，通過遞歸來完成，此時在遞歸時，我們只會去計算會對原問題有用的子問題，這樣就可以避免這個問題了。那么，我們通過遞歸方式來計算：
// i代表的是物品序號，W代表的是背包容量
int knapsack(const vector<int>& w, const vector<int>& p, int i, int W)
{
// 沒有選擇物品
if (i == 0) return 0;
// 遞歸關系
if (w[i - 1] > W) return knapsack(w, p, i - 1, W);
return max(knapsack(w, p, i - 1, W),
p[i - 1] + knapsack(w, p, i - 1, W - w[i - 1]));
}
有了遞歸關系，遞歸函數寫起來總是那么簡單。但是上面的遞歸沒有利用查詢表，這樣會重復計算子問題。所以，我們還是要修改一下，但是此時我們不再使用二維數組作為查詢表，因為實際上并不需要計算那么多子問題。我們可以使用關聯容器來作為查詢表：
// i代表的是物品序號，W代表的是背包容量
int knapsack(const vector<int>& w, const vector<int>& p,
int i, int W, map<pair<int, int>, int>& table)
{
pair<int, int> item{ i, W };
// 重復利用
if (table.find(item) != table.end())
{
return table[item];
}
// 沒有選擇物品
if (i == 0) { table[item] = 0; }
else if (w[i - 1] > W) { table[item] = knapsack(w, p, i - 1, W, table); }
else
{
table[item] = max(knapsack(w, p, i - 1, W, table),
p[i - 1] + knapsack(w, p, i - 1, W - w[i - 1], table));
}
return table[item];
}
我們使用上面的例子測試這個代碼，會發現確實只是計算了需要用到的子問題：
int main()
{
map<pair<int,int>, int> table;
vector<int> w{ 5, 10, 20 };
vector<int> p{ 50, 60, 140 };
cout << knapsack(w, p, 3, 30, table) << endl;
for (auto& i : table)
{
cout << i.first.first << ',' << i.first.second << ': ' << i.second << endl;
}
return 0;
}
輸出：
200
0,0: 0
0,5: 0
0,10: 0
0,15: 0
0,20: 0
0,25: 0
0,30: 0
1,0: 0
1,10: 50
1,20: 50
1,30: 50
2,10: 60
2,30: 110
3,30: 200
此時，“自上而下”的遞歸實現就顯得有優勢，但是遞歸可能需要較深的棧。所以，還是視情況定吧。背包問題就說這么多了。
這里我們介紹一個復雜一點的例子，就是最短路徑算法。考慮這樣的場景，當兩個城市之間沒有直飛的航班時，如何選擇一個最短路線。要解決這個問題，我們首先要把它抽象出來，這就要涉及到圖模型了。圖（graph）由頂點（vertice）與邊（edge）組成，所以我們一般將圖模型用G(E,V)表示。這里，每個頂點可以代表一個城市，而邊代表兩個城市之間的路線，一般邊會有權重值，比如代表距離，這時就稱為有權圖。我們可以用一個矩陣來表示一個包含個頂點的加權圖，這個矩陣的每個元素為：
這種表示方法為鄰接矩陣法。我們的問題是現在要找出每個頂點到其它頂點的最短路徑。假如用來表示從頂點到頂點的最短路徑的長度，那么我們就是要計算出這個矩陣。我們先從這個矩陣的一個元素開始，比如我們要求。我們是否可以采用動態規劃來求解呢？就是我們想求頂點到頂點的最短路徑，我們怎么能分解這個問題。考慮這樣的情況，頂點到頂點的路徑的所有情況是使用頂點集，即使用頂點集作為頂點到頂點的路徑的中間頂點。我們如果不斷減少這個中間頂點集，那么問題規模會減小。這里我們將使用頂點集為作為中間頂點時，頂點到頂點的最短路徑長記為。那么它與使用頂點集作為中間頂點的最短路徑長有沒有關系呢？我們可以這樣考慮，如果加了頂點可作為中間頂點，可能會出現兩種情況：
就這兩種情況，所以可以取兩種情況的最小值就是最短路徑：
我們得到了遞歸關系，但是情況有點復雜。因為原來我們僅關注這個頂點到頂點的最短路徑，遞歸關系式中明顯要使用其他頂點之間的最短路徑。但是這不是問題。因為我們可以采用”自下而上“的策略，先計算較小的實例。首先我們的可以從最小值開始計算，其實就是，而且對每一個，我們先從最小的和開始計算。這樣需要三層循環，所以算法復雜度為。而且計算到最后，即時，就是頂點到頂點的最短路徑的長度。具體的實現如下：
// 最短路徑
void minPath(const vector<vector<int>>& W, vector<vector<int>>& D)
{
int n = W.size(); // 頂點總數
D = W; // 存儲最短路徑，此時是k=0的結果
// k = 1開始
for (int k = 1; k <= n; ++k)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
D[i][j] = min(D[i][j], D[i][k - 1] + D[k - 1][j]);
}
}
}
}
一個運行實例為：
int main()
{
const int INFITY = 10000;
vector<vector<int>> W{ {0, 1, INFITY, 1, 5},
{9, 0, 3, 2, INFITY} ,
{INFITY, INFITY, 0, 4, INFITY},
{INFITY, INFITY, 2, 0, 3 },
{ 3, INFITY, INFITY, INFITY, 0 } };
vector<vector<int>> D;
minPath(W, D);
for (auto& i : D)
{
for (auto j : i)
{
cout << j << ' ';
}
cout << '\n';
}
return 0;
}
輸出：
0 1 3 1 4
8 0 3 2 5
10 11 0 4 7
6 7 2 0 3
3 4 6 4 0
但是如果想具體知道頂點到頂點的最短路徑包含具體哪些中間頂點，你可以把這些中間頂點保存到一個數組中，然后利用遞歸的方式按順序輸出中間頂點，具體的實現如下：
// 最短路徑
void minPath(const vector<vector<int>>& W, vector<vector<int>>& D,
vector<vector<int>>& P)
{
int n = W.size(); // 頂點總數
D = W; // 存儲最短路徑，此時是k=0的結果
// 初始化P:保存中間節點
P = vector<vector<int>>(n, vector<int>(n, 0));
// k = 1開始
for (int k = 1; k <= n; ++k)
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (D[i][j] > D[i][k - 1] + D[k - 1][j]) // 不要使用>=
{
P[i][j] = k;
D[i][j] = D[i][k - 1] + D[k - 1][j];
}
}
}
}
}
// 輸出頂點start到頂點end最短路徑
void printPath(const vector<vector<int>>& P, int start, int end)
{
if (P[start - 1][end - 1] != 0) // 有中間節點
{
// 先輸出中間節點前的頂點
printPath(P, start, P[start - 1][end - 1]);
// 輸出中間節點
cout << P[start - 1][end - 1] << '->';
// 輸出中間節點后的頂點
printPath(P, P[start - 1][end - 1], end);
}
}
int main()
{
const int INFITY = 10000;
vector<vector<int>> W{ {0, 1, INFITY, 1, 5},
{9, 0, 3, 2, INFITY} ,
{INFITY, INFITY, 0, 4, INFITY},
{INFITY, INFITY, 2, 0, 3 },
{ 3, INFITY, INFITY, INFITY, 0 } };
vector<vector<int>> D;
vector<vector<int>> P;
minPath(W, D, P);
cout << '頂點5到頂點3的最短路徑長為: ' << D[4][3];
cout << '，最短路徑為: 5->';
printPath(P, 5, 3);
cout << '3\n';
return 0;
}
輸出：
頂點5到頂點3的最短路徑長為: 4，最短路徑為: 5->1->4->3
利用遞歸的方式，我們可以輸出兩個頂點之間的最短路徑。但是，上面有一點要注意，就是在比較D[i][j]與 D[i][k - 1] + D[k - 1][j]時，不要使用等號，這不會影響D的結果，但是會造成P錯誤。因為當k-1==i或者k-1==j時，會取等號，但是此時沒有意義，因為k不再是中間節點，而是端點。所以根據P利用遞歸方式輸出路徑就會有誤。最后，這里我們采用“自下而上”的策略，那么使用'自上而下“的遞歸方式是否可以呢？大家不妨試試。。。不過我覺得“自下而上”的方式是最合適的，因為我們這里是求得所有頂點之間的最短路徑，而且它們之間相關聯，那么所有的子問題都是需要計算的。
最后一個例子是最長遞增子序列（longest increasing subsequence , LIS），我們首先定義問題：給定一個整數序列，我們想找到其最長的遞增子序列，一個遞增子序列要滿足且。假如序列為，那么其最長遞增子序列為。一個需要的情況是最長遞增子序列可能不唯一。如果我們采用暴力窮舉法的話，那么時間復雜度為。如果我們想使用動態規劃的方法來解決這個問題，那么必須要將問題拆解。拆解倒是很簡單：由序列的最長遞增子序列是否可以求解序列的最長遞增子序列。好像并沒有直接關系。但是我們會想一下前面的最短路徑問題，一旦我們選擇了某個給定的中間頂點，那么最短路徑只與兩個子路徑的最優解有關。這可以借鑒，我們先求出序列以結束的最長遞增子序列，這里記為，那么我們有可能遞推出。因為對應的最長遞增子序列的右端點是，其前面的相鄰元素可能是中的一個，對于任何一種選擇，我們都可以計算出（這里第二個子序列固定為，要滿足，故其最長遞增子序列長度為1），我們不必糾結到底是是哪個，因為直接取所有情況的最大值就好了：
一旦我們計算出包含個元素的一維數組，取其最大值就是原問題的最長遞增子序列的長度。基于上面的想法，我們采用“自下而上”的方案實現：
int lis(const vector<int>& s)
{
vector<int> ls(s.size(), 0);
// 對于k=1
ls[0] = 1; // 只有一個元素
for (int i = 1; i < s.size(); ++i)
{
ls[i] = 1; // 僅含有自己
for (int j = 0; j < i; ++j)
{
if (s[j] <= s[i] && ls[i] < 1 + ls[j])
{
ls[i] = 1 + ls[j];
}
}
}
return *max_element(ls.begin(), ls.end());
}
實現包含兩層循環，所以算法復雜度為。如果我們想得到最長遞增子序列，可以利用類似的想法，使用一個數組存儲中間節點位置：
vector<int> lis(const vector<int>& s)
{
vector<int> ls(s.size(), 0);
vector<int> ps(s.size(), -1);
// 對于k=1
ls[0] = 1; // 只有一個元素
ps[0] = -1; // 無前接緊鄰節點
for (int i = 1; i < s.size(); ++i)
{
ls[i] = 1; // 僅含有自己
ps[i] = 0; // 無前接緊鄰節點
for (int j = 0; j < i; ++j)
{
if (s[j] <= s[i] && ls[i] < 1 + ls[j])
{
ls[i] = 1 + ls[j];
ps[i] = j;
}
}
}
int pos = max_element(ls.begin(), ls.end()) - ls.begin(); // lis的最后一個元素位置
vector<int> result;
result.push_back(s[pos]);
while (ps[pos] != -1)
{
pos = ps[pos];
result.push_back(s[pos]);
}
reverse(result.begin(), result.end());
return result;
}
上面的算法復雜度為，其實我們有比這個效率更高的解法。讓我們回顧一下前面的遞歸關系，當我們計算時，我們要把所有的情況都要遍歷一遍，因為并不知道哪種情況是最優的。假如序列的LIS長度為，那么如果我們知道這個序列中長度分別為遞增子序列末尾元素的最小值，這里遞增子序列長度為的末尾元素最小值記為。當你加入元素時，如果，那么說可以直接加入這個LIS為的序列后面，此時對于序列其最大LIS為，且。如果，你需要遍歷，直到找到第一個滿足所對應的，然后更新，這時我們更新只是維持數組的特性，這樣后面繼續加入新元素，可以重復前面的過程，但是其實元素的加入并不會為當前整個序列的LIS做貢獻。大家可能會想，這樣操作其實也需要兩層循環。但是我們要注意一個細節，那就是其實是非遞減序列，即，所以內部遍歷時，我們可以使用二分搜索法，這樣算法的最終復雜度為。但是要注意，最后的序列不一定是一個最長遞增子序列，準確地說，序列的每個元素指的是長度為的遞增子序列的最后一個元素的最小值。但是序列的長度是等于最大遞增子序列的長度。具體的實現如下：
vector<int> lis(const vector<int>& s)
{
vector<int> m;
// 初始化
m.push_back(s[0]);
for (int i = 1; i < s.size(); ++i)
{
// lis增加1
if (s[i] >= m.back())
{
m.push_back(s[i]);
}
else
{
// 利用lower_bound函數找到第一個大于或等于s[i]的位置
*lower_bound(m.begin(), m.end(), s[i]) = s[i];
}
}
return m;
}
這種處理很巧妙，看來動態規劃靈活的地方太多了。
動態規劃只是一種思想，并無定型，這是我的感受。網上有人說遞推關系不是動態規劃的本質，說動態規劃的本質是狀態轉移方程。其實感覺還是一回事。遞推式也罷，狀態轉移方程也好。要想使用動態規劃，你需要首先學會分解問題，然后想著如何利用分解的問題解來計算當前解，當然最終的目的是提升效率。還有一點，就是兩種思維模式：“自下而上”與“自下而上”。還是多多練習，才是王道。
[1] Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, fourth edition, 2013.
[2] Richard E. Neapolitan, Foundations of Algorithms, fifth edition, 2016.
[3] Dynamic Programming 筆記.
[4] 渡部有隆（日）著， 支鵬浩 譯，挑戰程序設計競賽2：算法和數據結構, 2016.
