DP

将大问题分为小问题进行解决，从而一步步获取最优解

• 刻画一个最优解的特征结构
• 递归定义最优解的值
• 计算最优解的值，通常采用自底而上的方法
• 利用计算出的信息构造一个最优解

数字三角形搜索树

• 定义状态$(i, j)$的函数$f(x, y)$为从格子$(i, j)$出发时能得到的最大和，包括$(i, j)$本身
• 原问题的解是$(i, j)$
• 状态转移方程：$f(i, j) = a(i, j) +max(f(i + 1, j), f(i + 1, j + 1))$

int i, j;
for (j = 1; j <=n; j++) f[n][j] = a[n][j];
for (i = n - 1; i >= 1; i--) for (j = 1; j <= i; j ++) f[i][j] = a[i][j] + max(f[i + 1][j], f[i + 1][j + 1])

例题：POJ3176

#include<iostream>
#include<cstdio>
#define MAXN 351
using namespace std;
int way[MAXN][MAXN], dp[MAXN][MAXN];
int N;

int main(){
    cin >> N;
    for (int i = 1; i <= N; i++) for (int j = 1; j <= i; j++) cin >> way[i][j];
    for (int j = 1; j <= N; j++) dp[N][j] = way[N][j];
    for (int i = N - 1; i >= 1; i--) {
        for (int j = 1; j <= i; j ++) dp[i][j] = way[i][j] + max(dp[i + 1][j], dp[i + 1][j + 1]);
    }
    cout << dp[1][1] << endl;
    return 0;
}

01背包

n个重量价值为$w_i, v_i$的物品，选出总重量不超过W的物品，求价值总和最大值

状态转移方程（正推）： $$ dp[i][j] = \begin{cases} 0, i = n;\cr dp[i + 1][j], i < w[i];\cr max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]), else; \end{cases} $$

状态转移方程（正推）： $$ dp[i + 1][j] = \begin{cases} 0, i = 0;\cr dp[i][j], i < w[i];\cr max(dp[i][j], dp[i][j - w[i]] + v[i]), else; \end{cases} $$

int n, w;
int w[MAX_N], v[MAX_N];
int mem[MAX_N + 1][MAX_W + 1], dp[MAX_N + 1][MAX_W + 1], dp1[MAX_W + 1];

//暴搜
int rec(int i, int j){
    if (i == n) return 0;
    else if (j < w[i]) return rec(i + 1, j);
    else return max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
}

//记忆化搜索
int rec_mem(int i, int j){
    if (mem[i][j] >= 0) return mem[i][j]
    if (i == n) return 0;
    else if (j < w[i]) return rec(i + 1, j);
    else return max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);
}

void solve(){
    memset(mem, -1, sizeof(mem));
    printf("%d\n", rec(0, w));
    printf("%d\n", rec_mem(0, w));
    //dp反推
    for (int i = n - 1; i >= 0; i--){
        for (int j = 0; j < W; j++){
            if (j < w[i]) dp[i][j] = dp[i + 1][j];
            else dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);
        }
    }
    printf("%d\n", dp[n][W]);

    memset(dp, 0, sizeof(dp));
    //dp正推
    for (int i = 0; i < n; i++){
        for (int j = 0; j < W; j++){
            if (j < w[i]) dp[i + 1][j] = dp[i][j];
            else dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
        }
    }
    printf("%d\n", dp[n][W]);
    //一维dp
    for (int i = 0; i < n; i) for (int j = W; j >= w[i]; j--) dp1[j] = max(dp1[j], dp1[j - w[i]] + v[i]);
    printf("%d\n", dp[W]);
}

例题：POJ3624

#include<iostream>
#include<cstring>
#include<cstdio>
#define N 3410
#define M 13000
using namespace std;

int dp[M];

int main(){
    int n, m;
    int v[M], w[N];
    while (~scanf("%d%d", &n, &m)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
        for (int i = 1; i <= n; i++) for (int j = m; j >= w[i]; j--) dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
        printf("%d\n", dp[m]);
    }
    return 0;
}

例题：POJ1837

#include<iostream>
using namespace std;
int C, G;
int dp[21][15001];
int loc[21];
int w[21];

int main(){
    cin >> C >> G;
    for (int i = 1; i <= C; i++) cin >> loc[i];
    for (int i = 1; i <= G; i++) cin >> w[i];
    dp[0][7500] = 1;
    for (int i = 1; i <= G; i++){
        for (int j = 1; j <= 15000; j++){
            for (int k = 1; k <= C; k++) dp[i][j] += dp[i - 1][j - w[i] * loc[k]];
        }
    }
    cout << dp[G][7500] << endl;
}

完全背包

递推关系：$dp[i + 1][j]$：从前i种物品中挑选总重量不超过j时总价值的最大值 $$ dp[i + 1][j] = \begin{cases} 0, i = 0;\cr max(dp[i][j], dp[i][j - k \cdot w[i]] + k \cdot v[i]), else \end{cases} $$

int dp[MAX_N + 1][MAX_W + 1];

void solve(){
    for (int j = 0; i < n; i++){
        for (int j = 0; j <= W; j++){
            for (int k = 0; k * w[i] <= j; k++) dp[i + 1][j] = max(dp[i][j], dp[i][j - k * w[i]] + k * v[i]);
        }
    }
    printf("%d\n", dp[n][W]);
}

当$j > w[i]$时， $dp[i + 1][j] = dp[i + 1][j - w[i]] + v[i]$

void solve(){
    for (int j = 0; i < n; i++){
        for (int j = 0; j <= W; j++){
            if (j < w[i]) dp[i + 1][j] = dp[i][j];
            else dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
        }
    }
    printf("%d\n", dp[n][W]);
}
//一维
void solve(){
    for (int i = 0; i < n; i++) for (int j = w[i]; j <= W; j++) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    printf("%d\n", dp[W]);
}

使用同一数组实现时，01背包：从后往前推；完全背包：从前往后推

例题：POJ1384

#include<stdio.h>
#include<algorithm>
#define inf 100000000   
using namespace std;

int dp[11000];
int p[600];
int w[600];

int main(){
    int k, n, e, f;
    scanf("%d", &k);
    while (k--){
        scanf("%d", &e);
        scanf("%d", &f);
        int diff = f - e;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++){
            scanf("%d", &p[i]);
            scanf("%d", &w[i]);
        }
        for(int i = 0; i <= diff; i++) dp[i] = inf;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) for (int j = w[i]; j <= diff; j++) dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
        if (dp[diff] == inf) printf("This is impossible.\n");
        else printf("The minimum amount of money in the piggy-bank is %d.\n",dp[diff]);
    }
}

以w为dp对象：

$dp[i + 1][j]$表示前i个物品中挑出总价值为j时总重量的最小值

int dp[MAX_N + 1][MAX_N * MAX_V + 1];
const int INF = 0xffffff

void solve(){
    fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF);
    dp[0][0] = 0;
    for (int j = 0; i < n; i++){
        for (int j = 0; j <= MAX_N * MAX_V; j++){
            if (j < v[i]) dp[i + 1][j] = dp[i][j];
            else dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
        }
    }
    int res = 0;
    for (int i = 0; i <= MAX_N * MAX_V; i++) if (dp[n][i] <= W) res = i;
    printf("%d", res);
}

最长公共子序列

$dp[i][j] = s_1, ... , S_i, t_1, ... , t_j$对应LCS长度

1. $s_{i + 1} = t_{j + 1}$, 末尾dp

$$ dp[i + 1][j + 1] = \begin{cases} dp[i][j] + 1, s1[i] = s2[j];\cr max(dp[i + 1][j], dp[i][j + 1]), else \end{cases} $$

例题：POJ1458

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1000 + 5;
int n, m;
int dp[maxn][maxn];
char s1[maxn], s2[maxn];

int main(){
    while (scanf("%s%s", s1, s2) == 2){
        n = strlen(s1);
        m = strlen(s2);
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <=m; j++){
                if (s1[i] == s2[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
                else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        printf("%d\n", dp[n][m]);
    }
    return 0;
}

最长上升子序列

$dp[i] = max(1, dp[i - 1])$

例题：POJ3903

#include<cstdio>
#include<algorithm>
using namespace std;

int dp[100010];
int a[100010];

int main(){
    int N;
    while (scanf("%d", &N) != EOF){
        int ans = 0;
        for (int i = 0; i < N; i++) scanf("%d", &a[i]);
        for (int i = 0; i < N; i++){
            dp[i] = 1;
            for (int j = 0; j < i; j++) if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
            ans = max(ans, dp[i])
        }
        printf("%d\n", ans);
    }
}

多重部分和

int n; 
int K;
int a[MAX_N];
int m[MAX_N];
bool dp[MAX_N + 1][MAX_K + 1];
void solve(){
    dp[0][0] = 1;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < K; j++){
            for (int k = 0; k <= m[i] && k * a[i] <= j; K++) dp[i + 1][j] |= dp[i][j - k * a[i]];
        } 
    }
    if (dp[n][k]) printf("yes\n");
    else printf("no\n");
}

int n; 
int a[MAX_N];
int m[MAX_N];
bool dp[MAX_K + 1];
void solve(){
    memset(dp, -1, sizeof(dp));
    dp[0] = 1;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < K; j++){
            if (dp[j] >= 0) dp[j] = m[i];
            else if (j < a[i] || dp[j - a[i]] <= 0) dp[j] = 0;
            else dp[j = dp[j - a[i]]] - 1;
        } 
    }
    if (dp[k] >= 0) printf("yes\n");
    else printf("no\n");
}

例题：POJ1742

#include<iostream>
#include<cstring>
using namespace std;

int num[105]; 
int price[105];
int dp[100005];

int main(){
    int n, m;
    while (cin >> n >> m && (n || m)){
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; i++) cin >> price[i];
        for (int i = 0; i < n; i++) cin >> num[i];
        dp[0] = 0;
        for (int i = 0; i < n; i++){
            for (int j = 0; j <= m; j++){
                if (dp[j] >= 0) dp[j] = num[i];
                else if (j < price[i] || dp[j - price[i]] <= 0) dp[j] = -1;
                else dp[j] = dp[j - price[i]] - 1;
            }
        }
        int sum = 0;
        for (int i = 1; i <= m; i++) if (dp[i] >= 0) sum++;
        cout << sum << endl;
    }
    return 0;
}