1所袁、 什么樣的問題適合用動態(tài)規(guī)劃來求解
1.1. 問題具有最優(yōu)子結(jié)構(gòu)；就是說問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的旅赢；比如數(shù)字三角形問題中對于第i行j列的元素來說宛蚓，其到i+1行的最優(yōu)路徑是確定的即：max(dp[i+1][j], dp[i+1][j+1])激捏。
1.2. 狀態(tài)具有無后效性；即當(dāng)前的若干個(gè)狀態(tài)值一旦確定凄吏，則此后過程的演變就只和這若干個(gè)狀態(tài)的值有關(guān)远舅，和之前是采取哪種路徑演變到當(dāng)前的這若干個(gè)狀態(tài)，沒有關(guān)系竞思。
2表谊、 動態(tài)規(guī)劃問題解題的一般思路
1、將原問題分解為子問題
- 把原問題分解為若干個(gè)子問題盖喷，子問題和原問題形式類似爆办，只是規(guī)模變小，子問題都解決了的話课梳，原問題也就解決了距辆；
- 子問題的解一旦求出就會被保存，所以每個(gè)子問題只用求解一次暮刃；
- 比如數(shù)字三角形問題中某個(gè)元素對應(yīng)的最優(yōu)路徑的最大和就是一個(gè)子問題跨算；
2、確定狀態(tài)
- 將和子問題相關(guān)的各變量的一組取值椭懊，稱為一個(gè)“狀態(tài)”诸蚕；一個(gè)狀態(tài)對應(yīng)于一個(gè)或多個(gè)子問題，所謂某個(gè)狀態(tài)下的值氧猬，就是這個(gè)狀態(tài)所對應(yīng)的子問題的解背犯；所有狀態(tài)的集合就構(gòu)成了問題的狀態(tài)空間，狀態(tài)空間的大小盅抚，與動規(guī)解決問題的時(shí)間復(fù)雜度相關(guān)漠魏；
- 比如數(shù)字三角形問題中每個(gè)元素對應(yīng)的最優(yōu)路徑的最大和就是一個(gè)狀態(tài)，總共有N*(N+1)/2個(gè)狀態(tài)妄均，乘以每個(gè)狀態(tài)計(jì)算所需的時(shí)間就是整個(gè)問題的求解時(shí)間柱锹；
3哪自、確定邊界狀態(tài)值
- 比如數(shù)字三角形問題中邊界值就是三角形底邊的值；
4禁熏、確定狀態(tài)轉(zhuǎn)移方程
- 如何從一個(gè)或多個(gè)值已知的狀態(tài)壤巷，求出另一個(gè)狀態(tài)的值，（“人人為我”遞推型）匹层。狀態(tài)的轉(zhuǎn)移可以用遞推公式表示隙笆，此公式就叫狀態(tài)轉(zhuǎn)移方程；
- 比如數(shù)字三角形問題中的狀態(tài)轉(zhuǎn)移方程：
if(start_raw == n-1)//邊界條件
max_sum[start_raw][start_col] = nums[start_raw][start_col];
else
int max_1 = maxSum(nums, start_raw + 1, start_col, n);
int max_2 = maxSum(nums, start_raw + 1, start_col + 1, n);
int max = max_1 >= max_2 ? max_1 : max_2;
max_sum[start_raw][start_col] = max + nums[start_raw][start_col];
3 實(shí)例講解
例題一升筏、 數(shù)字三角形
題目描述：
如下圖所示的數(shù)字三角形圖，尋找從頂至底的某處的一條路徑瘸爽，使該路徑所經(jīng)過的數(shù)字之和最大您访。（1）每一步只能沿左斜線向下或右斜線向下，只需要給出最大和就可以了剪决，不必給出具體路徑（2）1 < 三角形行數(shù) < 101（3）三角形數(shù)字為0灵汪，1，…99
image.png
解法方法分析：
- 首先構(gòu)建輸入：該數(shù)據(jù)是三角形柑潦，屬于二維圖形享言，適合使用二維向量或是數(shù)組來表示；
可以使用如下代碼來實(shí)現(xiàn)
#include<iostream>
#include<vector>
using namespace std;
void getInput(vector<vector<int> >& dp_test)
{
vector<vector<int> > dp_test;
cout << "enter raw num: " << endl;
int raw_n;
cin >> raw_n;
int input;
for(int raw = 0; raw < raw_n; raw++)
{
vector<int> temp_vector;
for(int col = 0; col < raw+1; col++)
{
cout << "enter the numbers" << endl;
cin >> input;
temp_vector.push_back(input);
}
dp_test.push_back(temp_vector);
}
cout << "The raw num is: " << raw_n << endl;
cout << "The input nums are: " << endl;
for(size_t i = 0; i < dp_test.size(); I++)
{
for(size_t j = 0; j < dp_test[i].size(); j++)
{
cout << dp_test[i][j] << " ";
}
cout << endl;
}
}
得到的數(shù)組是這樣的
The raw num is: 5
The input nums are:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
這里元素dp[i][j], i和j從0開始渗鬼，每次向下移動的路徑就是dp[i+1][j]或者dp[i+1][j+1];maxSum(i,j)表示從dp[i][j]到底邊的各條路徑中览露，最佳路徑的數(shù)字和；
- 解法一譬胎、 該問題是典型的遞歸問題
從dp[i][j]出發(fā)差牛，下一步只能走dp[i+1][j]或者dp[i+1][j+1]，即只要知道maxSum(i+1,j)和maxSum(i+1,j+1)就能得到maxSum(i,j) = max(maxSum(i+1,j),maxSum(i+1,j+1)) + dp[i][j]堰乔；邊界就是maxSum(n-1,*) = nums[n-1][*]
int maxSum(vector<vector<int>> nums, int start_raw, int start_col, int n)
{
if(start_raw == n-1)//邊界條件
return nums[start_raw][start_col];
int max_1 = maxSum(nums, start_raw + 1, start_col, n);
int max_2 = maxSum(nums, start_raw + 1, start_col + 1, n);
int max = max_1 >= max_2 ? max_1 : max_2;
return max + nums[start_raw][start_col];
}
int main()
{
vector<vector<int>> input_vec;
getInput(input_vec);
cout << maxSum(input_vec, 0, 0, input_vec.size()) << endl;
return 0;
}
分析遞歸算法的時(shí)間復(fù)雜度偏化，該遞歸方法是從上到下一層一層的遞歸求解，那么存在大量的重復(fù)計(jì)算镐侯，每個(gè)元素上面重復(fù)計(jì)算的次數(shù)如下入所示：
image.png
根據(jù)等比數(shù)列求和可該算法的時(shí)間復(fù)雜度是O(2^n),對于n=100行侦讨，時(shí)間肯定是超時(shí)的；
- 解法二苟翻、 記憶遞歸型動規(guī)程序韵卤，采用遞歸的方式，時(shí)間復(fù)雜度太大主要是因?yàn)閮?yōu)太多的重復(fù)計(jì)算袜瞬，改進(jìn)的方法是將計(jì)算出的每一個(gè)maxSum值都存起來怜俐，下次用到的時(shí)候直接取用，避免重復(fù)計(jì)算邓尤；那么這時(shí)的時(shí)間復(fù)雜度根據(jù)等差數(shù)列求和可以知道是O(n^2);
#include<iostream>
#include<vector>
using namespace std;
void getInput(vector<vector<int>>& dp_test, vector<vector<int>>& dp_max)
{
vector<vector<int> > dp_test;
cout << "enter raw num: " << endl;
int raw_n;
cin >> raw_n;
int input;
for(int raw = 0; raw < raw_n; raw++)
{
vector<int> temp_vector;
vector<int> max_vector;
for(int col = 0; col < raw+1; col++)
{
cout << "enter the numbers" << endl;
cin >> input;
temp_vector.push_back(input);
max_vector.push_back(-1);
}
dp_test.push_back(temp_vector);
dp_max.push_back(max_vector);
}
}
int maxSum(vector<vector<int>> nums, int start_raw, int start_col, int n, vector<vector<int>> max_sums)
{
if(max_sums[start_raw][start_col] != -1)
return max_sums[start_raw][start_raw];
if(start_raw == n-1)//邊界條件
{
max_sums[start_raw][start_col] = nums[start_raw][start_raw];
}
else
{
int max_1 = maxSum(nums, start_raw + 1, start_col, n, max_sums);
int max_2 = maxSum(nums, start_raw + 1, start_col + 1, n, max_sums);
int max = max_1 >= max_2 ? max_1 : max_2;
max_sums[start_raw][start_col] = max + nums[start_raw][start_col];
}
}
int main()
{
vector<vector<int>> input_vec;
vector<vector<int>> max_vec;
getInput(input_vec,max_vec);
cout << maxSum(input_vec, 0, 0, input_vec.size(), max_vec) << endl;
return 0;
}
- 解法三拍鲤、遞推（“人人為我”遞推型動歸程序）
遞歸會有調(diào)用棧溢出的風(fēng)險(xiǎn)贴谎；可以使用遞推的方式，即從最后一行開始季稳，逐層向上求出每個(gè)元素位置的最大值擅这，這樣既可以每個(gè)元素只計(jì)算一次，時(shí)間復(fù)雜度為O(2^n),又不使用遞歸景鼠，不會有調(diào)用棧溢出的風(fēng)險(xiǎn)仲翎；采用遞推時(shí)，最后一行的最大值就是自己铛漓，倒數(shù)第二行的最大值時(shí)元素本身加上最后一行兩個(gè)數(shù)的最大值溯香，上面的行以此類推，結(jié)果如下：
輸入數(shù)據(jù)：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
遞推后的結(jié)果：
| 30 | ||||
|---|---|---|---|---|
23 |
21 | |||
20 |
13 | 10 | ||
| 7 | 12 |
10 | 10 | |
| 4 | 5 |
2 | 6 | 5 |
上面的表格過程可以看出來浓恶，整個(gè)過程會從底向上求出每一個(gè)節(jié)點(diǎn)在以該節(jié)點(diǎn)開始到最下面的最優(yōu)路徑的解玫坛；這個(gè)值只是該節(jié)點(diǎn)的最優(yōu)解，并不是該層的最優(yōu)解包晰，但是當(dāng)我們以此方式求到最上面的節(jié)點(diǎn)即頂點(diǎn)時(shí)湿镀，頂點(diǎn)的最優(yōu)解就是我門需要的最優(yōu)解；這里不需要記錄路徑伐憾；
#include<iostream>
#include<vector>
using namespace std;
/*
@dp_max:的元素對于每一行都是復(fù)用的
*/
void getInput(vector<vector<int>>& dp_test, vector<int>& dp_max)
{
vector<vector<int> > dp_test;
cout << "enter raw num: " << endl;
int raw_n;
cin >> raw_n;
int input;
for(int raw = 0; raw < raw_n; raw++)
{
vector<int> temp_vector;
for(int col = 0; col < raw+1; col++)
{
cout << "enter the numbers" << endl;
cin >> input;
temp_vector.push_back(input);
}
dp_test.push_back(temp_vector);
for(auto iter : dp_test[raw_n - 1])
dp_max.push_back(iter);
}
}
int maxSum(vector<vector<int>> nums, int start_raw, int start_col, int n, vector<int> max_sums)
{
for(int raw = n - 1; raw > start_raw - 1; raw--)
{
for(int col = 0; col < n; col++)
{
int max = nums[raw + 1][col] >= nums[raw + 1][col+1] ? nums[raw + 1][col] : nums[raw + 1][col + 1];
max_sums[col] = max + nums[raw][col];
}
}
return max_sums[start_col];
}
int main()
{
vector<vector<int>> input_vec;
vector<int> max_vec;
getInput(input_vec,max_vec);
cout << maxSum(input_vec, 0, 0, input_vec.size(), max_vec) << endl;
return 0;
}
- 遞歸到動規(guī)程序的一般轉(zhuǎn)換方法
- 遞歸函數(shù)有n個(gè)參數(shù)勉痴，就定義一個(gè)n維的數(shù)組，數(shù)組的下標(biāo)是遞歸函數(shù)參數(shù)的取值范圍树肃，數(shù)組元素的值時(shí)遞歸函數(shù)的返回值蒸矛，這樣就可以從邊界開始，逐步填充數(shù)組扫外，這就相當(dāng)于計(jì)算遞歸函數(shù)值的逆過程莉钙。
例題二、 最長公共子序列
題目描述：
給出兩個(gè)字符串筛谚，求出這樣的一 個(gè)最長的公共子序列的長度:子序列 中的每個(gè)字符都能在兩個(gè)原串中找到磁玉， 而且每個(gè)字符的先后順序和原串中的 先后順序一致。
解法方法分析：
首先拿到題目驾讲，是求最優(yōu)解的題目蚊伞，一般用dp來解，但是dp需要有無后效性的最優(yōu)子問題吮铭，這個(gè)需要好好設(shè)計(jì)dp的狀態(tài)时迫，設(shè)計(jì)不出來就不能用dp；
首先想到的是對于長度為m和n的兩個(gè)字符串S1和S2谓晌，其
- 狀態(tài)：最長公共子序列用
dp(m,n)表示掠拳； - 那么顯然邊界條件：
dp(i,0) = 0; (i = 0...m)
dp(0,j) = 0; (j = 0...n)
- 狀態(tài)轉(zhuǎn)移方程
當(dāng)S1[i-1] == S2[j-1]時(shí)這時(shí)顯然的：dp(i, j) = dp(i-1, j-1) + 1;
當(dāng)S1[i-1] != S2[j-1]時(shí)有：dp(i, j) = max(dp(i-1,j), dp(i, j-1))
屏幕快照 2019-11-19 上午12.34.52的副本.png
- 顯然dp(i, j)不會比dp(i-1,j)和dp(i, j-1)小纸肉；
- 那么會不會比兩個(gè)都大呢溺欧？假設(shè)dp(i, j)比dp(i-1,j)大喊熟，因?yàn)槎呶ㄒ徊煌木褪荢1[i-1]，那么S1[i-1]一定是S1和S2的最長公共子序列的最后一個(gè)元素姐刁；同理芥牌，假設(shè)dp(i, j)比dp(i,j-1)大，那么S2[j-1]一定是S1和S2的最長公共子序列的最后一個(gè)元素聂使；那么必然S1[i-1] == S2[j-1]壁拉，而這個(gè)于假設(shè)沖突，所以可以得到上面的狀態(tài)轉(zhuǎn)移方程柏靶；
-
采用遞推的方式實(shí)現(xiàn)
屏幕快照 2019-11-19 上午12.40.12.png
image.png
int longestCommonSubsequence(string text1, string text2) {
if(text1.size() == 0 || text2.size() == 0){
return 0;
}
int len1 = text1.size();
int len2 = text2.size();
vector<vector<int>> lcs;
lcs.resize(len1 + 1);
for(size_t i = 0; i <= len1; i++){
lcs[i].push_back(0);
lcs[i].resize(len2 + 1);
}
for(size_t j = 1; j <= len2; j++){
lcs[0][j] = 0;
}
for(size_t i = 1; i <= len1; i++){
for(size_t j = 1; j <= len2; j++){
if(text1[i-1] == text2[j-1]){
lcs[i][j] = lcs[i-1][j-1] + 1;
} else {
lcs[i][j] = lcs[i-1][j] > lcs[i][j-1] ? lcs[i-1][j] : lcs[i][j-1];
}
}
}
return lcs[len1][len2];
}
