做了一部分的動態壓縮的題目，來整理歸納一下，
（僅僅是以初學者的視角出發，還有很多不足和欠缺的地方，也希望各路大神指正，以后遇到新的dp類問題再來補充吧(っ °Д °;)っ）
動態規劃主要應用于解決最優解的問題，這類問題往往具有區域最優子結構，一般的dp還由重復子問題，而且存在僅依賴于前一個或者前幾個狀態的狀態遷移方程，利用分治與遞回的演算法思想，可以實作動態規劃自底向上的實作結果的求解，
動態規劃的優點：
動態規劃的優點主要在于其在實作以遞回為基礎的演算法時，避免使用函式層層遞回的結構，而是跳脫出來利用陣列存盤和雙重回圈來進行記憶化遞回，從而在需要的時候直接呼叫該結果，避免無用的重復計算，提高程式執行的效率，
經典DP例題決議與實作：
比如經典的斐波那契數列，就可以簡單得通過動態規劃來實作，避免了重復的遞回和深度的過度挖掘，
請看代碼：
/* 動態規劃演算法思想實作斐波那契 記憶化遞回 回圈展開實作 區域->整體 */
#include <iostream>
using namespace std;
const int maxn = 50 + 5;
int main() {
int n;
cin >> n;
int F[maxn];
F[1] = F[2] = 1;
for (int i = 3; i <= n; i++) {
F[i] = F[i - 1] + F[i - 2];
}
cout << F[n] << endl;
return 0;
}如果不用回圈的動態規劃，而是普通的遞回，則會做很多無用功，效率大打折扣，
int fibonacci(n)
if n==0||n==1
return 1
return fibonacci(n-2)+fibonacci(n-1)在這類動態規劃中，遞推公式（也可以叫狀態轉移方程）的建立是實作dp的基礎，也是關鍵，
比如下面這一道經典的最長公共子序列的動態規劃的題目（LCS），要求倆個字串X、Y的最長公共子序列，由題意得出如下的遞推方程，那么這一道題可以輕松解決，
自己優化完成的代碼如下：
/* LCS 問題framework Dynamic Programming 回圈展開&記憶化遞回 分治與遞回求解最優解 */
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1000 + 5;
int lcs(string x, string y) {
int m = x.length();
int n = y.length();
x = ' ' + x;
y = ' ' + y;
int dp[maxn][maxn];
memset(dp, 0, sizeof(dp));
int ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (x[i] == y[j]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
ans = max(ans, dp[i][j]);
}
}
return ans;
}
int main() {
int n;
string x, y;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x >> y;
cout << lcs(x, y) << endl;
}
return 0;
}類似地，這一道非常非常經典的矩陣鏈乘法的程設題目也同樣地可以類似得解決，另外，在這里要補充一點，在決議矩陣鏈乘法的數學運算式的時候，可以借助stack這樣一個資料結構巧妙得實作，
同樣是最優解，具有區域最優子結構，分析可得：
在得出本題的遞推公式的時候，對數學分析也提出了一定的要求，代碼實作充分體現題意和資料內涵，精妙優化如下：
/* 矩陣鏈乘最優解Framework DP 回圈實作&記憶化遞回 分治與遞回 數學分析 細節處理代碼簡化 */
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 100 + 5;
int main() {
int n;
cin >> n;
int p[maxn];
int dp[maxn][maxn];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) {
cin >> p[i - 1] >> p[i];
}
for (int l = 2; l <= n; l++) {
for (int i = 1; i <= n - l + 1; i++) {
int j = i + l - 1;
dp[i][j] = 1 << 25;
for (int k = i; k < j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]);
}
}
}
cout << dp[1][n] << endl;
return 0;
}另外，所有的DP一定別忘了預處理與初始化，這很重要！o(￣┰￣*)ゞ
以上是一般的經典DP，掌握了這樣的設計或者編程技巧，我們的動態規劃可以到更高一層，
高階的狀態遷移DP
硬幣問題，在普通的硬幣問題中，若面值類似于1、5、10、50、100等，在求所付硬幣的最少枚數的時候，可以逐步減去最大面值，基于一直貪心法，但當面值隨機且不定變化的時候，這種情況下的最優解就需要借助dp了，還是具有區域最優子結構的，請看狀態遷移方程：
解決關鍵是抽象出遞推模型，對于每一種狀態都可以找到前一種狀態來對應或者遷移，
代碼如下，很精簡，也很好理解，帶入每一個變數和結構的被賦予的具體實際應用意義即可：
/* 硬幣問題的動態規劃 回圈遍歷下的記憶化遞回 最優解 狀態轉移方程 編程技巧 */
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1 << 30;
const int N = 50000 + 5;
const int M = 20 + 5;
int mon[M];
int dp[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int c;
cin >> c;
mon[i] = c;
}
for (int i = 0; i < N; i++) {
dp[i] = maxn;
}
dp[0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j + mon[i] <= n; j++) {
dp[j + mon[i]] = min(dp[j + mon[i]], dp[j] + 1);
}
}
cout << dp[n] << endl;
return 0;
}再來看一道再熟悉不過的經典DP吧，0—1背包問題（應該是背包系列最簡答的一個模型了）
最優解問題的抽象具備了“0-1”特征（埋個伏筆，下面將會有大量與0-1有關的二進制dp系列問題哦o(￣┰￣*)ゞ） 代碼上吧：
（很精簡，沒有給出具體注釋，只有頭注釋，請讀者不妨花點時間自己盡情感受一下吧(#｀-_ゝ-)(#｀-_ゝ-)好吧，比較懶而已）
/* 經典0-1背包DP問題 “0-1”抽象的遞推特征與狀態轉移方程 遞回設計與最優解問題（區域最優子結構）標記陣列記錄選擇情況 */
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
struct item {
int value;
int weight;
};
const int nmax = 100 + 5;
const int mmax = 10000 + 5;
int n, w;
item items[nmax];
int dp[nmax][mmax];
int g[nmax][mmax];
void compute(int &maxvalue, vector<int> &selection) {
for (int i = 0; i <= w; i++) {
dp[0][i] = 0;
g[0][i] = 1;
}
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
dp[i][j] = dp[i - 1][j];
g[i][j] = 0;
if (items[i].weight > j)continue;
if (items[i].value + dp[i - 1][j - items[i].weight] > dp[i - 1][j]) {
dp[i][j] = items[i].value + dp[i - 1][j - items[i].weight];
g[i][j] = 1;
}
}
}
maxvalue = dp[n][w];
selection.clear();
for (int i = n, j = w; i >= 1; i--) {
if (g[i][j]) {
selection.push_back(i);
j -= items[i].weight;
}
}
reverse(selection.begin(), selection.end());
}
int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
items[i].value = x;
items[i].weight = y;
}
memset(dp, 0, sizeof(dp));
memset(g, 0, sizeof(g));
int maxvalue;
vector<int> selection;
compute(maxvalue, selection);
cout << maxvalue << endl;
for (vector<int>::iterator it = selection.begin(); it != selection.end(); it++) {
cout << *it << " ";
}
cout << "\n";
return 0;
}再來一道吧，應該有感覺了吧，
最大正方形，不多廢話，一樣的板子，直接來方程和代碼：
/* 最大正方形 動態規劃的本質特征 狀態轉移 預處理 遞回與分治 */
//a.動態規劃：區域最優子結構 大問題分解位區域小問題
//b.狀態轉移：某一步的狀態可由或者僅由其前一步或者前幾步推導 即可進行狀態轉移 可寫出狀態轉移方程
//記憶化遞回：有了a b的條件基礎既可實作dp，記憶區域最優解，自底向上回圈至整個最優解
#include <iostream>
using namespace std;
const int maxn = 1500;
int dp[maxn][maxn];
int graph[maxn][maxn];
int H, W;
int min(int x, int y, int z) {
if (x < y) {
if (x < z) return x;
else return z;
}
else {
if (y < z)return y;
else return z;
}
}
int max(int x, int y) {
return (x > y ? x : y);
}
int getlargestsquare() {
int maxwidth = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
dp[i][j] = (graph[i][j] + 1) % 2;
maxwidth |= dp[i][j];
}
}
for (int i = 1; i < H; i++) {
for (int j = 1; j < W; j++) {
if (graph[i][j]) {
dp[i][j] = 0;
}
else {
dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1;
maxwidth = max(maxwidth, dp[i][j]);
}
}
}
return maxwidth*maxwidth;
}
int main() {
cin >> H >> W;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> graph[i][j];
}
}
cout << getlargestsquare() << endl;
return 0;
}（好了，基本動態規劃就先到這吧，待會會繼續補充一篇文章來記錄狀態壓縮動態規劃哦，也就是前面的伏筆啦（＞人＜；），）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/342257.html
標籤：其他
上一篇：深入了解快排 以及 優化