## 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))$ ```cpp 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](https://vjudge.net/contest/703263#problem/A) ```cpp #include #include #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} $$ ```cpp 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](https://vjudge.net/contest/703263#problem/B) ```cpp #include #include #include #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](https://vjudge.net/contest/703263#problem/C) ```cpp #include 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} $$ ```cpp 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]$ ```cpp 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]() ```cpp #include #include #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时总重量的最小值 ```cpp 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]() ```cpp #include #include #include 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]() ```cpp #include #include 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); } } ``` ## 多重部分和 ```cpp 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"); } ``` ```cpp 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]() ```cpp #include #include 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; } ```

Schabe Antimonfeld

ACM-ICPC基础 动态规划方法

ACM-ICPC基础动态规划方法