動態規劃學習筆記（1）

記錄一下慕課學習的筆記，以及例題代碼

一。遞歸到動規的一般轉化方法#

遞歸函數有 n 個參數就定義一個 n 維的數組，數組的下標是遞歸函數參數的取值範圍。
這樣就可以從邊界值開始逐步填充數組，相當於計算遞歸函數值的逆過程。eg：例題 1 數字三角形

二。動規解題的一般思路#

1. 將原問題分解為子問題#

將原問題分解為若干個子問題，與原問題的形式相同或類似，只不過規模小了。
子問題都解決，原問題即解決。
子問題的解一旦求出就會被保存，所以每個子問題只要求解一次。

2. 確定狀態#

狀態：往往把和子問題相關的各個變量的一組取值稱為一個狀態。一個狀態對應於一個或多個子問題。
值：所謂某個狀態下的值就是這個狀態所對應的子問題的解。
時間複雜度：整個問題的時間複雜度是狀態數目乘以每個狀態所需時間。
存儲：若 K 個整型變量能夠構成一個狀態，且取值範圍分別為 N1,N2,……,Nk，我們就可以用一個 K 維的數組 array [N1][N2]……[Nk] 來存儲各個狀態的 “值”，這個值未必是一個整數或浮點數，甚至可能是需要一個結構表示的，故 array 可以是一個結構數組。

3. 確定一些初始狀態 (邊界狀態) 的值#

4. 確定狀態轉移方程#

定義出什麼是狀態，以及在該狀態下的值後，就要找出不同的狀態之間如何遷移。
即如何從一個或多個值已知的狀態推出另一個狀態的值("人人為我" 遞推型)。狀態的遷移可以用遞推公式表示，此遞推公式也可稱作 "狀態轉移方程"。

三。能用動規解決的問題的特點#

1) 問題具有最優子結構性質#

最優子結構性質：如果問題的最優解所包含的子問題的解也是最優的，稱其具有該性質。

2) 無後效性#

當前的若干個狀態值一旦確定，則此後過程的演變就只和這若干個狀態的值有關，與之前是採取哪種手段或經過哪條路徑演變到當前這若干個狀態無關。

四。例題#

例題 1. 數字三角形#

題意

: 給定一個由 n 行數字組成的數字三角形如下圖所示。試設計一個算法，計算出從三角形的頂至底的一條路徑，使該路徑經過的數字總和最大。
對於給定的由 n 行數字組成的數字三角形，計算從三角形的頂至底的路徑經過的數字和的最大值。
輸入數據的第 1 行是數字三角形的行數 n，1≤n≤100。接下來 n 行是數字三角形各行中的數字。所有數字在 0..99 之間。
輸出數據只有一個整數，表示計算出的最大值。

示例輸入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

示例輸出

30

代碼 1 記憶遞歸型動歸程序

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//用遞歸的話會超時 重複計算太多
//所以將每次遞歸的結果算出來存到數組裡
//叫做記憶遞歸型動歸程序
int D[MAX][MAX];//D[r][j]表示第r行第j個數字(r,j從1開始算)
int maxSum[MAX][MAX];//從D(r,j)到底邊的各條路徑中，最佳路徑的數字之和
int n;
int MaxSum(int i, int j) {
    if (maxSum[i][j] != -1)
        return maxSum[i][j];//若maxSum的值有被算過
    if (i == n) 
        maxSum[i][j] = D[i][j];
    else {
        int x = MaxSum(i+1, j);
        int y = MaxSum(i+1, j+1);
        maxSum[i][j] = max(x, y) + D[i][j];
    }
    return maxSum[i][j];
}
int main(){
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            cin >> D[i][j];
            maxSum[i][j] = -1;
        }
    }
    cout << MaxSum(1, 1) << endl;
    return 0;
}

代碼 2 循環遞推式動態規劃

#include <iostream>
#include <algorithm>
#define MAX 101
using namespace std;
//循環  遞推式 動態規劃
int D[MAX][MAX];//D[r][j]表示第r行第j個數字(r,j從1開始算)
int maxSum[MAX][MAX];//從D(r,j)到底邊的各條路徑中，最佳路徑的數字之和
int n;
int main(){
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= i; j++) {
            cin >> D[i][j];
            maxSum[i][j] = -1;
        }
    }
    for (i = 1; i <= n; i++)
        maxSum[n][i] = D[n][i];
    for (i = n-1; i >= 1; i--) {
        for (j = 1; j <= i; j++) {
            maxSum[i][j] = 
                max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j];
        }
    }
    cout << maxSum[1][1] << endl;
    return 0;
}

例題 2. 神奇的口袋#

題意

有一個神奇的口袋，總的容積是 40，用這個口袋可以變出一些物品，這些物品的總體積必須是 40。John 現在有 n 個想要得到的物品，每個物品的體積分別是 a1，a2……an。John 可以從這些物品中選擇一些，如果選出的物體的總體積是 40，那麼利用這個神奇的口袋，John 就可以得到這些物品。現在的問題是，John 有多少種不同的選擇物品的方式。

輸入輸出

輸入:
3
20
20
20
輸出:
3

代碼

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[30]; int N;
int Ways[40][30];//Ways[i][j]表示從j種物品裡凑出體積i的方法數
int main() {
    cin >> N;
    memset(Ways, 0, sizeof(Ways));
    for (int i = 1; i <= N; ++i) {
        cin >> a[i]; Ways[0][i] = 1;
    }
    Ways[0][0] = 1;
    for (int w = 1; w <= 40; w++) {
        for (int k = 1; k <= N; k++) {
            Ways[w][k] = Ways[w][k-1];
            if (w-a[k] >= 0)
                Ways[w][k] += Ways[w-a[k]][k-1];
        }
    }
    cout << Ways[40][N];
    return 0;
}

例題 3. 最長公共子序列#

題意

給出兩個字符串求一個最長的公共子序列的長度

輸入輸出

輸入:
abcfbc abfcab
programming contest
abcd mnp
輸出:
4
2
0

代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1001][1001];
/*思路:設dp(i,j)表示s1左邊i個字符形成的子串
與s2左邊j個字符形成的字串的最長公共子序列的長度
dp(n,0) = 0, dp(0,n) = 0; 
if (s1[i-1] == s2[j-1]) dp(i,j) = dp(i-1,j-1) + 1;
else dp(i, j) = max(dp(i,j-1), dp(i-1,j));*/
int main() {
    string s1, s2;
    cin >> s1 >> s2;
    int len1 = s1.length();
    int len2 = s2.length();
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <=len2; j++) {
            if(s1[i-1] == s2[j-1]) 
                dp[i][j] = dp[i-1][j-1] + 1;
            else 
                dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
    }
    cout << dp[len1][len2] << endl;
    return 0;
}

例題 4. 最長上升子序列#

題意

輸入第一行序列的長度 N，第二行 N 個整數
輸出最長上升子序列的長度

輸入輸出

輸入樣例:
7
1 7 3 5 9 4 8
輸出樣例:
4

代碼

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
/*思路:分解為求以ak為終點的最長上升子序列的長度 ，maxLen(k)表示以ak為終點的最長上升子序列長度
為在ak左邊 且ai小於ak 長度最大的最長上升子序列的長度+1
因為ak左邊任何終值小於ak的子序列加上ak後就能形成一個更長的上升子序列*/
int a[maxn]; int maxLen[maxn];
int main() {
    int N, ans = -1;  cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> a[i]; maxLen[i] = 1;
    }
    for (int i = 2; i <= N; i++) {
        //每次求以第i個數為終點的最長上升子序列的長度
        for(int j = 1; j < i; j++) {
            //以第j個數為終點的最長上升子序列
            if (a[j] < a[i]) {
                maxLen[i] = max(maxLen[i], maxLen[j]+1);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if(maxLen[i] > ans) ans = maxLen[i];
    }
    cout << ans << endl;
    return 0;
}
//時間複雜度O(N^2)

轉自慕課程序設計與算法（二）動態規劃 ppt