上一篇
算法設(shè)計與分析復(fù)習(xí)–遞歸與分治（二）
動態(tài)規(guī)劃性質(zhì)
與分析法類似：將原問題分解為子問題
不同點：不是通過遞歸的方式，而是自底向上的求解問題
矩陣連乘問題
矩陣連乘的次數(shù)是左矩陣行列，右矩陣行列取出左右中進行相乘。
由于矩陣乘積需要滿足左矩陣列等于右矩陣的行，所以可以用一維數(shù)組進行存n個矩陣，共n + 1個元素，從第一個矩陣的（1）行（2）列，第二個矩陣由于行與第一個的列相同就不在重復(fù)存儲所以只需存第二個的（3）列，一次類推
數(shù)據(jù)結(jié)構(gòu)：
a[N] 存矩陣行列
dp[N][N] => dp[i][j]表示第i個矩陣到第j個矩陣的最小連乘次數(shù)
因為是從小到大算每個區(qū)間內(nèi)的最小值=> 區(qū)間dp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int N = 110;
int a[N], dp[N][N], n;
void out()
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= n; j ++)
printf("%d ", dp[i][j]);
puts("");
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i <= n; i++) scanf("%d", &a[i]);
// 初始化dp數(shù)組
memset(dp, 0, sizeof(dp));
for(int len = 2; len <= n; len ++)
{
for (int i = 1; i + len - 1 <= n; i ++)
{
int j = i + len - 1;
dp[i][j] = 1e8; // 初始化為一個較大的值
for (int k = i; k < j; k ++)
{
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + a[i - 1] * a[k] * a[j]);
// out();
}
}
}
out();
printf("%d\n", dp[1][n]);
return 0;
}
區(qū)間DP類似題目 AcWing.282石子合并
凸多邊形最優(yōu)三角部分
問題描述
可以轉(zhuǎn)換成矩陣連乘問題
加完括號的形式就是那個最優(yōu)三角形的位置
數(shù)據(jù)結(jié)構(gòu)
v[N]: 表示每個結(jié)點對應(yīng)值
dp[N][N]: dp[i][j]表示結(jié)點從 i 到 j 的三角的權(quán)重，取min
狀態(tài)計算（區(qū)間dp）：
d
p
[
i
]
[
j
]
=
m
i
n
{
d
p
[
i
]
[
k
]
+
d
p
[
k
+
1
]
+
w
(
v
i
?
1
v
k
v
j
)
}
dp[i][j] = min\{ dp[i][k] + dp[k + 1] + w(v_{i-1}v_kv_j)\}
dp[i][j]=min{dp[i][k]+dp[k+1]+w(vi?1?vk?vj?)}
最長公共子序列
AcWing897.最長公共子序列
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
char a[N], b[N];
int dp[N][N], n, m;
int x[N][N];//尋路數(shù)組
vector<char> ans;
void out()
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
cout << dp[i][j] << ' ';
cout << endl;
}
cout << "*****************" << endl;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
cout << x[i][j] << ' ';
cout << endl;
}
cout << "*****************" << endl;
}
void trackback(int i, int j)
{
if (i <= 0 || j <= 0) return;
if (x[i][j] == 1){
ans.push_back(a[i]);
trackback(i - 1, j - 1);
}
else if (x[i][j] == 2) trackback(i - 1, j);
else trackback(i, j - 1);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
cin >> a + 1 >> b + 1;//因為有i - 1操作所以起始下標要從1開始防止數(shù)組越界
for(int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
if(a[i] == b[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
x[i][j] = 1;// 1表示i和j都要選為對應(yīng)公共元素
}
else if(dp[i - 1][j] >= dp[i][j - 1]){
dp[i][j] = dp[i - 1][j];
x[i][j] = 2;//回溯沿著表上走
}
else{
dp[i][j] = dp[i][j - 1];
x[i][j] = 3;//沿著表左走
}
}
}
out();
cout << dp[n][m] << endl;
trackback(n, m);
reverse(ans.begin(), ans.end());//答案順序反了，需要翻轉(zhuǎn)一下
for (auto i : ans)
cout << i;
return 0;
}
輸入順序?qū)懛戳?，列是第一個序列，行時第二個序列
0-1背包問題
AcWing2. 01背包
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N], w[N], v[N], n, c;
int main()
{
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i ++) scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= c; j ++)
{
dp[i][j] = dp[i - 1][j];
if(w[i] <= j) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
printf("%d", dp[n][c]);
return 0;
}
觀察發(fā)現(xiàn)狀態(tài)計算的方程中只用到了第i行和第i - 1行，所以可以用滾動數(shù)組，將這個二維數(shù)組優(yōu)化成一維數(shù)組
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N], w[N], v[N], n, c;
int main()
{
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i ++) scanf("%d%d", &w[i], &v[i]);
for (int i = 1; i <= n; i ++)
for (int j = c; j >= 1; j --)// 也可以將下面if條件拿到上面=> for(int j = c; j >= w[i]; j --)
{
if(w[i] <= j) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
printf("%d", dp[c]);
return 0;
}
帶結(jié)果回溯的寫法
如果用回滾數(shù)組就找不到對應(yīng)物品的坐標了，但是可以找到對應(yīng)價值的物品
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int dp[N][N], w[N], v[N], n, c;
int x[N][N];
void out()
{
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= c; j ++)
printf("%d ", dp[i][j]);
puts("");
}
puts("************");
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= c; j ++)
printf("%d ", x[i][j]);
puts("");
}
puts("************");
}
void trackback(int i, int j, int f)
{
if(i <= 0 || j <= 0) return;
if(f == 0){
printf("不選第%d件商品\n", i);
trackback(i - 1, j, x[i - 1][j]);
}
if(f == 1){
printf("選第%d件商品\n", i);
trackback(i - 1, j - w[i], x[i - 1][j - w[i]]);//選這件商品后的坐標需要算一下
}
}
int main()
{
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);
for (int i = 1; i <= n; i ++) scanf("%d", &v[i]);
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= c; j ++){
if(w[i] <= j && dp[i - 1][j] < dp[i - 1][j - w[i]] + v[i]){
dp[i][j] = dp[i - 1][j - w[i]] + v[i];
x[i][j] = 1;
}
else{
dp[i][j] = dp[i - 1][j];
x[i][j] = 0;
}
}
out();
printf("%d\n", dp[n][c]);
trackback(n, c, x[n][c]);
return 0;
}
圖像壓縮
像素點灰度值序列{
p
1
p_1
p1?,
p
2
p_2
p2?, …
p
n
p_n
pn?}表示圖像。
不同定長圖像每一位為8個bit
但是可以將灰度值存在變長字節(jié)中
但是變長存儲解藥進行解碼，所以要存儲解碼信息，第
i
i
i 端存了多少位要用幾位二進制來存。
較小值用較小的bit來存，較大值用較長bit來存。但是解壓縮要花的bit是固定的
11
?
m
??
b
i
t
是解壓縮固定的
b
i
t
(
m
表示劃分成幾段
)
11 * m\ \ bit是解壓縮固定的bit(m表示劃分成幾段)
11?m??bit是解壓縮固定的bit(m表示劃分成幾段)
數(shù)據(jù)結(jié)構(gòu)：
a
[
i
]
a[i]
a[i] 表示每個像素所占位數(shù)
l
[
i
]
l[i]
l[i] 表示劃分的第
i
i
i 段有
l
[
i
]
l[i]
l[i] 個像素
b
[
i
]
b[i]
b[i] 表示劃分的第
i
i
i 段用
b
[
i
]
b[i]
b[i] 位表示
其中一種劃分方式
s
[
i
]
s[i]
s[i]就是上面分析的
d
p
[
i
]
dp[i]
dp[i]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int a[N], s[N], n;
int l[N], b[N];//當前分組a[i]和前面共幾個為一段，比特多少
void out()
{
printf("a[i] : ");
for (int i = 1; i <= n; i ++)
printf("%d ", a[i]);
puts("");
printf("s[i] : ");
for (int i = 1; i <= n; i ++)
printf("%d ", s[i]);
puts("");
printf("l[i] : ");
for (int i = 1; i <= n; i ++)
printf("%d ", l[i]);
puts("");
printf("b[i] : ");
for (int i = 1; i <= n; i ++)
printf("%d ", b[i]);
puts("");
}
int get_max(int ed, int step)
{
int m = 0, i = ed;
while(step)
{
m = max(m, a[i]);
i --;
step --;
}
return m;
}
int main()
{
memset(s, 0x3f, sizeof s);
scanf("%d", &n);
for (int i = 1; i <= n; i ++){
int p;
scanf("%d", &p);
int t = 0;
while (p) t ++, p /= 2;
a[i] = t;
}
s[0] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
int maxa = get_max(i, j);
if(s[i - j] + j * maxa + 11 < s[i])
{
l[i] = j;
b[i] = maxa;
s[i] = s[i - j] + j * maxa + 11;
}
}
printf("最優(yōu)壓縮位數(shù)：%d\n", s[n]);
out();
return 0;
}
文章來源：http://www.zghlxwxcb.cn/news/detail-756926.html
下一篇
算法設(shè)計與分析復(fù)習(xí)–貪心（一）文章來源地址http://www.zghlxwxcb.cn/news/detail-756926.html
到了這里，關(guān)于算法設(shè)計與分析復(fù)習(xí)--動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
