二维动态规划降维误差一般为多少_动态规划 所有题型的总结
1 動(dòng)態(tài)規(guī)劃
1.1 定義
動(dòng)態(tài)規(guī)劃的核心是狀態(tài)和狀態(tài)轉(zhuǎn)移方程。
在記憶化搜索中，可以為正在處理的表項(xiàng)聲明一個(gè)引用，簡化對它的讀寫操作；
動(dòng)態(tài)規(guī)劃解決的是多階段決策問題；
初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
和分治法最大的區(qū)別在于：適合于用動(dòng)態(tài)規(guī)劃的問題，經(jīng)過分解以后得到的子問題往往不是相互獨(dú)立的(即下一個(gè)子階段的求解是建立在上一個(gè)子階段的基礎(chǔ)之上，進(jìn)行進(jìn)一步的求解，而不是相互獨(dú)立的問題)
動(dòng)態(tài)規(guī)劃問題一般由難到易分為一維動(dòng)態(tài)規(guī)劃，二維動(dòng)態(tài)規(guī)劃，多維動(dòng)態(tài)規(guī)劃，以及多變量動(dòng)態(tài)規(guī)劃問題。其中多維動(dòng)態(tài)規(guī)劃問題又可以進(jìn)行降維。動(dòng)態(tài)規(guī)劃問題求解的最重要的一步就是求解出 狀態(tài)轉(zhuǎn)移方程
1.2 特性
最優(yōu)化原理：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，就稱該問題具有最優(yōu)子結(jié)構(gòu)，即滿足最優(yōu)化原理.
無后效性：即某階段狀態(tài)一旦確定，就不受這個(gè)狀態(tài)以后決策的影響。也就是說，某狀態(tài)以后的過程不會(huì)影響以前的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)
有重疊子問題：即子問題之間是不獨(dú)立的，一個(gè)子問題在下一階段決策中可能被多次使用到。(該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢，動(dòng)態(tài)規(guī)劃可以避免多次計(jì)算)
1.3 例子
還是做題最實(shí)在!
1.3.1 最長公共子序列
問題描述：給定兩個(gè)序列：X[1...m]和Y[1...n]，求在兩個(gè)序列中同時(shí)出現(xiàn)的最長子序列的長度。
如果按照最普通的方法，就是遍歷所有可能的情況(將較短字符串中所有的子串和較長字符串中的子串進(jìn)行比較)，取所有可能的情況中最長的子串；
int DP::LongestCommonSubsequence(string &X, string &Y, int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (X[m-1] == Y[n-1]) {
return LongestCommonSubsequence(X, Y, m-1, n-1) + 1;
}
else {
return max(LongestCommonSubsequence(X, Y, m-1, n), LongestCommonSubsequence(X, Y, m, n-1));
}
}
void DP::testLongestCommonSubstring() {
string x = "abcdefg", y = "efg";
int result = LongestCommonSubsequence(x, y, (int)x.size(), (int)y.size());
cout << "result:" << result;
}
很顯然，這花費(fèi)的時(shí)間是指數(shù)級(jí)的，非常慢；
那么采用動(dòng)態(tài)規(guī)劃是怎么做的？
思路：我們可以想象成樹，兩個(gè)字符串都分別進(jìn)行發(fā)散，對于一個(gè)結(jié)點(diǎn)來說，左邊是左邊的字符串進(jìn)行改變，右邊則是右邊的字符串進(jìn)行改變，直到兩個(gè)字符串都相等。
第一步應(yīng)該是找出遞推公式：
這里的 C[i,j] 代表的意思是字符串 X 中到達(dá)下標(biāo) i 和字符串 Y 中到達(dá)下標(biāo) j 的時(shí)候的最長子串個(gè)數(shù)；
第二步是寫出偽代碼
LCS(x,y,i,j)
if x[i] = y[j]
then C[i,j] ← LCS(x,y,i-1,j-1)+1
else C[i,j] ← max{LCS(x,y,i-1,j),LCS(x,y,i,j-1)}
return C[i,j]
最后是寫出代碼
上面的偽代碼對于每一種情況都會(huì)往前重新計(jì)算一遍，完全沒有必要，用一個(gè)數(shù)組保存之前計(jì)算的值即可；
int DP::LongestCommonSubsequence(string &X, string &Y, int m, int n) {
vector> dp(X.size() + 1, vector(Y.size() + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 因?yàn)槭菑?開始的，所以字符串下標(biāo)要減去1
if (X[i-1] == Y[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
void DP::testLongestCommonSubsequence() {
string x = "abcdefg", y = "efg";
int result = LongestCommonSubsequence(x, y, (int)x.size(), (int)y.size());
cout << "result:" << result;
}
看看dp數(shù)組：
0 0 0 0 0 0
0 1 1 1 1 1
0 1 2 2 2 2
0 1 2 3 3 3
0 1 2 3 3 3
0 1 2 3 3 3
0 1 2 3 4 4
0 1 2 3 4 5
1.3.2 最長公共子串
和上面最長公共子序列不同的是，子串要求連續(xù)，不像子序列只要順序保證是正確的就行了，所以使用一個(gè)變量來記錄；
/**************************************
* // 最長公共子串問題
***************************************/
int DP::LongestCommonSubstring(string &X, string &Y, int m, int n) {
vector> dp(X.size() + 1, vector(Y.size() + 1, 0));
int max = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 因?yàn)槭菑?開始的，所以字符串下標(biāo)要減去1
if (X[i-1] == Y[j-1]) {
if (dp[i-1][j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
}
else {
dp[i][j] = 1;
}
if (dp[i][j] > max) {
max = dp[i][j];
}
}
}
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
cout << " " << dp[i][j];
}
cout << endl;
}
return max;
}
void DP::testLongestCommonSubstring() {
string x = "abcdefg", y = "abcfg";
int result = LongestCommonSubstring(x, y, (int)x.size(), (int)y.size());
cout << "result:" << result << endl;
}
看看dp數(shù)組：
0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 3 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 2
可以發(fā)現(xiàn)，對角線上連續(xù)大于0的值則為長度；最長的子串為abc，長度為3，次長為fg，長度為2；
1.3.3 最長遞增子序列
問題描述：給定一個(gè)序列：X[1...m]，求在這個(gè)序列中出現(xiàn)的最長遞增子序列的長度。
/**************************************
* // 最長遞增子串問題
***************************************/
int DP::LongestIncreasingSubstring(string &X, int m) {
vector dp(X.size(), 0);
int max = 0;
for (int i = 0; i < m; i++) { //到達(dá)
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (X[i] > X[j]) {
dp[i] = dp[j] + 1;
}
else { //因?yàn)槭沁B續(xù)的，所以只要不符合就重置
dp[i] = 1;
}
}
}
for (int i = 0; i < m; i++) {
cout << " " << dp[i];
if (dp[i] > max) {
max = dp[i];
}
}
cout << endl;
return max;
}
void DP::testLongestIncreasingSubstring() {
string x = "babcak";
int result = LongestIncreasingSubstring(x, (int)x.size());
cout << "result:" << result << endl;
}
1.3.4 矩陣鏈乘積
題目描述
給定n個(gè)矩陣｛A1,A2,…,An｝，其中Ai與Ai+1是可乘的，i=1，2…，n-1。如何確定計(jì)算矩陣連乘積的計(jì)算次序，使得依此次序計(jì)算矩陣連乘積需要的數(shù)乘次數(shù)最少。
思路
對于矩陣連乘問題，最優(yōu)解就是找到一種計(jì)算順序，使得計(jì)算次數(shù)最少；
假設(shè) dp[i, j] 表示第 i 個(gè)矩陣到達(dá)第 j 個(gè)矩陣這段的最優(yōu)解；
將矩陣連乘積 簡記為A[i:j] ，這里i<=j.假設(shè)這個(gè)最優(yōu)解在第k處斷開，i<=k
狀態(tài)轉(zhuǎn)移方程
當(dāng)i=j時(shí)，A[i,j]=Ai, m[i,j]=0;(表示只有一個(gè)矩陣,如A1,沒有和其他矩陣相乘,故乘的次數(shù)為0)
當(dāng)i
也就是
實(shí)現(xiàn)
/**************************************
* // 矩陣鏈乘積，求最小乘積次數(shù)
***************************************/
void DP::MatrixChainMultiplication(vector data, int n,vector>& m_dp, vector>& s_dp) {
//矩陣段長度為1,則 dp[][] 中對角線的值為0,表示只有一個(gè)矩陣,沒有相乘的.
for(int i = 1;i<=n;i++)
m_dp[i][i] = 0;
// 從第二個(gè)開始(第一個(gè)也是0)，當(dāng)前的乘次數(shù)取決于下一個(gè)的乘次數(shù)
// 對角線循環(huán)，r表示矩陣的長度(2,3…逐漸變長)
for(int r = 2;r<=n;r++) {
// 行循環(huán)
for(int i = 1; i<=n-r+1; i++) {
// 列的控制，當(dāng)前矩陣段(Ai~Aj)的起始為Ai,尾為Aj
int j = r+i-1;
//例如對(A2~A4),則i=2,j=4,下面一行的m[2][4] = m[3][4]+p[1]*p[2]*p[4],即A2(A3A4)
m_dp[i][j] = m_dp[i+1][j] + data[i-1]*data[i]*data[j]; //計(jì)算次數(shù)
s_dp[i][j] = i;//記錄斷開點(diǎn)的索引
//循環(huán)求出(Ai~Aj)中的最小數(shù)乘次數(shù)，遍歷所有可能的情況
for(int k = i+1 ; k
//將矩陣段(Ai~Aj)分成左右2部分(左m[i][k],右m[k+1][j])
//再加上左右2部分最后相乘的次數(shù)(p[i-1] *p[k]*p[j])
int t = m_dp[i][k] + m_dp[k+1][j] + data[i-1] *data[k]*data[j];
if(t < m_dp[i][j]) {
m_dp[i][j] = t;
s_dp[i][j] = k; //保存最小的,即最優(yōu)的結(jié)果
}
}
}
}
}
void DP::testMatrixChainMultiplication() {
vector data = {30,35,15,5,10,20,25};//記錄6個(gè)矩陣的行和列，注意相鄰矩陣的行和列是相同的
vector> m_dp(7, vector(7, 0));//存儲(chǔ)第i個(gè)矩陣到第j個(gè)矩陣的計(jì)算代價(jià)(以乘法次數(shù)來表示)
vector> s_dp(7, vector(7, 0));//存儲(chǔ)第i個(gè)矩陣到第j個(gè)矩陣的最小代價(jià)時(shí)的分為兩部分的位置
int n=6;//矩陣個(gè)數(shù)
MatrixChainMultiplication(data, n , m_dp, s_dp);
cout << "---計(jì)算代價(jià)---" << endl;
for (int i = 0; i < m_dp.size(); i++) {
for (int j = 0; j < m_dp[0].size(); j++) {
cout << " " << m_dp[i][j];
}
cout << endl;
}
cout << "---最小代價(jià)時(shí)分為兩邊的位置" << endl;
for (int i = 0; i < s_dp.size(); i++) {
for (int j = 0; j < s_dp[0].size(); j++) {
cout << " " << s_dp[i][j];
}
cout << endl;
}
}
運(yùn)行結(jié)果為：
---計(jì)算代價(jià)---
0 0 0 0 0 0 0
0 0 15750 7875 9375 11875 15125
0 0 0 2625 4375 7125 10500
0 0 0 0 750 2500 5375
0 0 0 0 0 1000 3500
0 0 0 0 0 0 5000
0 0 0 0 0 0 0
---最小代價(jià)時(shí)分為兩邊的位置
0 0 0 0 0 0 0
0 0 1 1 3 3 3
0 0 0 2 3 3 3
0 0 0 0 3 3 3
0 0 0 0 0 4 5
0 0 0 0 0 0 5
0 0 0 0 0 0 0
表示第i個(gè)矩陣到第j個(gè)矩陣的計(jì)算代價(jià)矩陣m[i][j]和表示第i個(gè)矩陣到第j個(gè)矩陣的最小代價(jià)時(shí)的分為兩部分的位置矩陣s[i][j]的結(jié)果如下圖：
從上面左圖的m矩陣可以看出任意第i個(gè)到第j個(gè)矩陣連乘的乘法次數(shù)。最終的加括號(hào)形式為：(A1(A2A3))((A4A5)A6)
1.3.5 數(shù)塔問題
問題描述：
數(shù)塔第i層有i個(gè)結(jié)點(diǎn)，要求從頂層走到底層，若每一步只能走到相鄰的結(jié)點(diǎn)，則經(jīng)過的結(jié)點(diǎn)的數(shù)字之和最大是多少？
用二維數(shù)組則為：
9
1215
1068
2 1895
19710416
假設(shè)9首先被輸入，是第 0 層，越往下層數(shù)不斷遞增；
思路
為了保證整條路徑的和是最大的，下一層的走向取決于再下一層上的最大值是否已經(jīng)求出才能決定，所以要做一個(gè)自頂向下的分析，自底向上的計(jì)算；
狀態(tài)轉(zhuǎn)移方程
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + data[i][j]
dp[i+1][j] 為左結(jié)點(diǎn)，dp[i+1][j+1] 為右結(jié)點(diǎn)；
實(shí)現(xiàn)
/**************************************
* // 數(shù)塔問題
***************************************/
int DP::MaxSumTower(vector> nums, int m, int n) {
vector> dp(m, vector(n, 0));
// 用底層的值來初始化dp，m為行，n為列
for (int i = 0; i < n; i++) {
dp[m-1][i] = nums[m-1][i];
}
// 自底向上，父結(jié)點(diǎn)的最大值取決于左結(jié)點(diǎn)或者右結(jié)點(diǎn)的最大值
for (int i = m-2; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (i >= j) { //過濾多余的
dp[i][j] = std::max(dp[i+1][j], dp[i+1][j+1]) + nums[i][j];
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << " " << dp[i][j];
}
cout << endl;
}
return dp[0][0];
}
1.3.6 01背包問題
題目描述
有編號(hào)分別為a,b,c,d,e的五件物品，它們的重量分別是2,2,6,5,4，它們的價(jià)值分別是6,3,5,4,6，現(xiàn)在給你個(gè)承重為10的背包，如何讓背包里裝入的物品具有最大的價(jià)值總和？
思路
dp[x][y] 表示體積不超過 y 且可選前 x 種物品的情況下的最大總價(jià)值
遞歸關(guān)系：
mp[0][y] = 0
mp[x][0] = 0
當(dāng) v[x] > y 時(shí)，mp[x][y] = mp[x-1][y]
當(dāng) v[x] <= y 時(shí)，mp[x][y] = max{ mp[x-1][y], p[x] + mp[x-1][y-v[x]] }
解釋如下：
表示體積不超過 y 且可選前 0 種物品的情況下的最大總價(jià)值，沒有物品可選，所以總價(jià)值為 0
表示體積不超過 0 且可選前 x 種物品的情況下的最大總價(jià)值，沒有物品可選，所以總價(jià)值為 0
因?yàn)?x 這件物品的體積已經(jīng)超過所能允許的最大體積了，所以肯定不能放這件物品， 那么只能在前 x-1 件物品里選了
x 這件物品可能放入背包也可能不放入背包，所以取前兩者的最大值就好了， 這樣就將前兩種情況都包括進(jìn)來了
實(shí)現(xiàn)
/**************************************
* // 01背包問題
***************************************/
int DP::ZeroOneBackpack(vector goods, int limit_weight) {
int m = goods.size();
int n = limit_weight;
vector> dp(m + 1, vector(n + 1, 0));
// 沒有選擇物品的時(shí)候價(jià)值為0
for (int i = 1; i < n; i++) {
dp[0][i] = 0;
}
// 重量為0的時(shí)候什么物品都選不了，價(jià)值自然也為0
for (int i = 1; i < m; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (goods[i-1].weight > j) { //超出限制的重量
dp[i][j] = dp[i-1][j];
}
else { //可能放入背包也可能不放入背包，取兩者情況的最大值
dp[i][j] = std::max(dp[i-1][j], dp[i-1][j - goods[i-1].weight] + goods[i-1].value);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cout << " " << dp[i][j];
}
cout << endl;
}
return dp[m][n];
}
void DP::testZeroOneBackpack() {
vector goods;
goods.emplace_back(0, 0);
goods.emplace_back(60, 10);
goods.emplace_back(100, 20);
goods.emplace_back(120, 30);
int result = ZeroOneBackpack(goods, 50);
cout << "result:" << result << endl;
}
1.3.7 最大連續(xù)子序列之和
問題描述：給定一個(gè)序列：X[1...m]，求在這個(gè)序列中出現(xiàn)的最大的連續(xù)子序列之和。
狀態(tài)轉(zhuǎn)移方程
dp[i] = std::max(dp[i-1] + nums[i], nums[i]);
實(shí)現(xiàn)
/**************************************
* // 最大連續(xù)子序列和
***************************************/
int DP::MaxContinusSubsequenceSum(int* nums, int m) {
vector dp(m, 0);
int max = INT_MIN;
dp[0] = nums[0];
for (int j = 1; j < m; j++) {
dp[j] = std::max(dp[j-1] + nums[j], nums[j]);
}
for (int i = 0; i < m; i++) {
cout << " " << dp[i];
if (dp[i] > max) {
max = dp[i];
}
}
cout << endl;
return max;
}
void DP::testMaxContinusSubsequenceSum() {
int data[] = {
1,-2,3,-1,7
};
int result = MaxContinusSubsequenceSum(data, 5);
cout << "result:" << result << endl;
}
總結(jié)
以上是生活随笔為你收集整理的二维动态规划降维误差一般为多少_动态规划 所有题型的总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： cad打印字体颜色很淡_收藏|50个CA
- 下一篇： 打印机可以打印不能扫描怎么弄_为什么打印