Dynamic Programming Algorithm

动态规划的常见模型与技巧，涵盖线性 DP、区间 DP、树形 DP、状态压缩 DP、数位 DP 等典型类型，重点介绍最长公共子序列、最长上升子序列、01 背包及其扩展（完全背包、多重背包、混合背包），并深入讲解状态设计、转移方程、边界初始化、滚动数组优化及单调队列优化等核心技巧。

线性DP

理解题目递推的顺序

守望者的逃离摆花线段乌龟棋最长公共子序列

s1 = io[0]; s2 = io[1];
n = s1.length(); m = s2.length();
dp = new int[n+1][m+1];
for (int i = 1;i <= n;i++){
    for (int j = 1;j <= m;j++){
        if (s1.charAt(i-1) == s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1]+1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
}
out.println(dp[n][m]);

P1439 【模板】最长上升子序列

把题目转换一下两个序列其中一个转换为1 2 … n 排列置换另一个计算最长上升子序列即可

O(n²)

static int[] a = new int[N], dp = new int[N]; //dp[i] 以i结尾最长递增子序列长度
static void solve() throws Exception {
n = ni();
for (int i = 1;i <= n;i++) a[i] = ni();
for (int i = 1;i <= n;i++){
    dp[i] = 1; //初始化 
    for (int j = i-1;j >= 1;j--){
        // 遍历之前的 如果大于a[j] 就更新取最大值
        if (a[i] > a[j]) dp[i] = max(dp[i], dp[j]+1); 
    }
}
int ans = 0; // 最长递增子序列长度不一定在末尾取到 所以要遍历所有下标
for (int i = 1;i <= n;i++) ans = max(ans, dp[i]);
out.println(ans);
}

优化：原来的dp数组的存储由数值换成该序列中，上升子序列长度为i的上升子序列，的最小末尾数值

这其实就是一种近贪心的思想：我们当前的上升子序列长度如果已经确定，那么如果这种长度的子序列的结尾元素越小，后面的元素就可以有更大概率地加入到这条上升子序列中。

O(nlog n)

static int[] a = new int[N], dp = new int[N];
//dp[i] : 长度为i+1的上升子序列中末尾最小的数值
static void solve() throws Exception {
    n = ni();
    for (int i = 1;i <= n;i++) a[i] = ni();
    Arrays.fill(dp, 0, n, 1<<30); //dp[i]存最小值 所以初始化为无穷
    int len = 0; // len表示最长上升子序列长度（答案）
    for (int i = 1;i <= n;i++){
        int cur = a[i];
        int l = 0, r = len-1; //二分找到第一个大于当前值的末尾值 用cur替换
        while (l <= r){
            int mid = l+r >> 1;
            if (dp[mid] < cur) l = mid+1;
            else r = mid-1;
        }
        if (l == len) ++len; //如果都小于当前值 说明子序列长度可以加1了
        dp[l] = min(dp[l], cur); //更新末尾最小值
    }
    out.println(len);
}

背包DP

01背包

static int[][] dp = new int[N][M];
static int[] w = new int[N], v = new int[N]; // w[i]:第i个物品体积 v[i]:第i个物品价
for (int i = 1;i <= n;i++){
    for (int j = 0;j <= m;j++){
        if (j >= w[i]) dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]);
        else dp[i][j] = dp[i-1][j];
    }
}
out.println(dp[n][m]);

static int[] dp = new int[M];
static int[] w = new int[N], v = new int[N]; // w[i]:第i个物品体积 v[i]:第i个物品价值
// dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j]); 第i行只与前一行有关，滚动数组优化
for (int i = 1;i <= n;i++){
    for (int j = m;j >= 0;j--){
        if (j >= w[i]) dp[j] = max(dp[j-w[i]]+v[i], dp[j]);
        //else dp[j] = dp[j];
    }
}
out.println(dp[m]);

P1048 采药 P1049 装箱问题

P1164 小A点菜计数问题：装满背包的方案数

static int[] dp = new int[M];
static int[] w = new int[N]; // w[i]:第i个物品体积
dp[0] = 1; //装满容量为0的背包方案数为1 就是什么都不装
for (int i = 1;i <= n;i++){
    for (int j = m;j >= 0;j--){
        if (j >= w[i]) dp[j] += dp[j-w[i]]; 
    }
}
out.println(dp[m]);

P1507 NASA的食物计划二维01背包（就又加了个限制条件而已）

int[][] dp = new int[M][M]; //从三维压缩到二维
int[] w1 = new int[N], w2 = new int[N], v = new int[N]; //w1:体积 w2:重量 v:价值
for (int i = 1;i <= n;i++){ 
    for (int j = m;j >= w1[i];j--){// 二维就多一个循环而已
        for (int k = t;k >= w2[i];k--) {
            dp[j][k] = max(dp[j-w1[i]][k-w2[i]]+v[i], dp[j][k]);
        }
    }
}
out.println(dp[m][t]);

完全背包

static int[] dp = new int[M];
static int[] w = new int[N], v = new int[N];
for (int i = 1;i <= n;i++){
for (int k = 0;k*w[i] <= m;k++){ //暴力 无限个物品 一一枚举 直接转换成01背包
    for (int j = m;j >= k*w[i];--j)
        dp[j] = max(dp[j], dp[j-k*w[i]]+k*v[i]);
    }
} //会TLE

// 完全背包正解
for (int i = 1;i <= n;i++){
    for (int j = w[i];j <= m;++j)
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
out.println(dp[m]);

首先考虑二维:dp[i][j] 怎么得到（其实就是上面写的暴力）

$两式联立即可导出$

考虑压缩到一维：

dp[i][j]更新要用到dp[i − 1][j], dp[i][j − v]

即第i层的j 要用到第i层的j − v来更新所以==第二层遍历顺序应该从小到大（与01背包的区别）==

USACO08NOV]Buying Hay S P1853 投资的最大效益

多重背包

暴力（物品可使用k次看成k个物品转换成01背包）多重背包问题 I

for (int i = 1;i <= n;i++) {
    for (int j = m;j >= v[i];j--) {
        for (int k = 1;k <= s[i] && j>=k*v[i];k++){
            dp[j] = max(dp[j], dp[j-k*v[i]]+k*w[i]);
        }
    }
}
out.println(dp[m]);

二进制优化多重背包问题 II

static int[] dp = new int[M];
static int[] w = new int[N], v = new int[N]; // N = N*Log(s) 
int cnt = 1;
for (int i = 1;i <= n;i++){
    int wi = ni(), vi = ni(), s = ni(); // 体积 价值 数量
    for (int c = 1;c <= s;c <<= 1){  // 二进制拆分
        w[cnt] = c*wi; v[cnt++] = c*vi; // 1 2 4 8 ... 个物品分别作为一组
        s -= c;
    }
    if (s != 0) {w[cnt] = s*wi; v[cnt++] = s*vi;} // 1 2 4 8...拆完可能还剩
}
for (int i = 1;i < cnt;i++){ //无脑01背包
    for (int j = m;j >= w[i];--j)
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
}
out.println(dp[m]);

单调队列优化 P1776 宝物筛选

混合背包

物品分三类：

第一类物品只能用 1 次（01背包）；
第二类物品可以用无限次（完全背包）；
第三类物品最多只能用 s 次（多重背包）；

static int[] dp = new int[M];
static int[] w = new int[N], v = new int[N], kind = new int[N]; //kind[]存背包类型
int n, m， cnt = 1;
for (int i = 1;i <= n;i++){
    int wi = ni(), vi = ni(), s = ni();
    if (s == 0){ 
        w[cnt] = wi; v[cnt] = vi; kind[cnt++] = 1;//无限次 完全背包 kind = 1
    }else{
        for (int k = 1;k <= s;k <<= 1){ //否则 多重背包转为01背包 kind = 0
            w[cnt] = wi*k; v[cnt] = vi*k; kind[cnt++] = 0;
            s -= k;
        }
        if (s != 0) {w[cnt] = wi*s; v[cnt] = vi*s; kind[cnt++] = 0;}
    }
}
for (int i = 1;i < cnt;i++){
    if (kind[i] == 0){ //完全背包
        for (int j = m;j >= w[i];--j) dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    }else{    //01背包
        for (int j = w[i];j <= m;++j) dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    }
}
out.println(dp[m]);

区间DP

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态 f(i, j) 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值，那么 f(i, j) = max {f(i, k) + f(k + 1, j) + cost}，cost 为将这两组元素合并起来的代价。

注意：f(i, j) 由 f(i, k) 和 f(k + 1, j) 得到所以直接两层循环i和j是不行的

比如 i循环到1 j循环到5 需要【1， 3】【4， 5】此时【4， 5】还没有求出来（因为i才循环到1）

所以我们要枚举区间长度从小到大

P1063 能量项链

for (int i = 1;i <= n;i++) {
    a[i-1][1] = a[i][0] = nl(); // a[i][0] a[i][1] 分别表示项链的首尾
    a[i-1+n] = a[i-1]; // 断环成链的技巧
}
a[n][1] = a[1][0];
long res = 0;
for (int len = 2;len <= n;len++){ //从小到大枚举区间长度 （1就不用枚举了 一个项链不好合并）
    for (int i = 1;i+len-1 < 2*n;i++){ //枚举左端点 注意要从1到2*n都要考虑
        int j = i+len-1; //算出右端点
        for (int k = i;k < j;k++){
            dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j]+
                            a[i][0]*a[k+1][0]*a[j][1]);
            if (dp[i][j] > res) res = dp[i][j];
        }
    }
}
out.println(res);

状态压缩DP

Cows in a Skyscraper G

给出n个物品，体积为w[i]，现把其分成若干组，要求每组总体积<=k，问最小分组。(n<=18)

我们用1代表这个奶牛已经在电梯里了,0则还没坐电梯

那么我们可以直接定义一维的数组,f[i]就代表当前状态为i时最小的乘电梯次数

最终的答案就是f[(1<<n)-1];

我们可以开一个数组g来记录当前状态下电梯内剩余的体积

static void solve() throws Exception {
n = ni(); k = ni();
for (int i = 0;i < n;i++) a[i] = ni();
Arrays.fill(dp, 1<<30);
dp[0] = 1; g[0] = k;
for (int i = 0;i < (1<<n);i++){//枚举状态 
    for (int j = 0;j < n;j++){//枚举每一头奶牛
        if ((i>>j & 1) == 1) continue;
        if (g[i] >= a[j]){//如果这个电梯坐得下
            dp[i | (1<<j)] = dp[i]; // 不用新开一个电梯
            g[i | (1<<j)] = max(g[i | (1<<j)], g[i]-a[j]);
        }else if (dp[i | (1<<j)] >= dp[i]+1) {//如果这个电梯坐不下 
            dp[i | (1<<j)] = dp[i]+1;// 新开一个电梯
            g[i | (1<<j)] = max(g[i | (1<<j)], k-a[j]);
        }
    }
}
out.println(dp[(1<<n)-1]);
}

数位DP

数位 DP：用来解决一类特定问题，这种问题比较好辨认，一般具有这几个特征：

要求统计满足一定条件的数的数量（即，最终目的为计数）；
这些条件经过转化后可以使用「数位」的思想去理解和判断；
输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
上界很大，暴力枚举验证会超时。

一般的数位dp中，任何为0的数位都对结果都不影响；但对于某些题目，最高位为0时，对结果不影响，但非最高位为0时会对答案有贡献；此时需要添加前导零标记，以用于判断当前位置是否为最高位。

windy 数

不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道，在 a 和 b 之间，包括 a和 b，总共有多少个 windy 数？

static int[] a = new int[N];
static int[][] d = new int[N][N];
// len表示已经搜到了第len位（从高到低 last表示前一位所填的数
// flag表示之前的每一位是否 都 已经紧贴上界 
// zero表示表示之前的每一位是否 都 是0
static int dfs(int len, int pre, boolean f, boolean z){
    if (len == 0) return 1; //全部遍历完了 返回1
    if (!f && !z && d[len][pre] != -1) return d[len][pre];
    //f为true, 那么当前位置最大只能够是区间上界数字的当前位的数值
    //否则,这一位能够填写0~9,因为这种情况下不管怎么填写,数字都不会超过给定范围.
    int res = 0, max = f?a[len]:9; 
    for (int i = 0;i <= max;i++){
        //条件:相邻两个数字之间的差值必须不小于2,并且是没有前导零的情况
        if (abs(i-pre) < 2 && !z) continue;
        res += dfs(len-1, i, f&&i==a[len], z&&i==0);
    }
    if (!f && !z) d[len][pre] = res;
    return res;
}
static int get(int x){ // 求区间[1, x] 满足条件的数的数量
    n = 0;
    while (x > 0){ // 把数拆成每一位
        a[++n] = x%10;
        x /= 10;
    }
    for (int i = 0;i < 11;i++) Arrays.fill(d[i], -1);
    return dfs(n, 11, true, true);
}
static void solve() throws Exception {
    int l = ni(), r = ni(); // 求区间[l, r] 满足条件的数量
    out.println(get(r)-get(l-1));
}

树形DP

树形 dp 的主要实现形式是 dfs ，在 dfs 中 dp ，主要的实现形式是 dp[i][j][2] 基本的 dp 方程选择节点类

树形背包类

P1352 没有上司的舞会

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r。但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

static int[] a = new int[N], dp[] = new int[N][2];
// f[x][0]表示以x为根,且x不参加的最大快乐值   f[x][1]表示以x为根，且x参加了的最大快乐值
static List<Integer>[] g = new List[N];
static void dfs(int u){
    dp[u][0] = a[u];
    for (int v : g[u]) {
        dfs(v); //自底向上遍历
        dp[u][0] += dp[v][1];
        dp[u][1] += max(dp[v][1], dp[v][0]);
    }
}

P2016 战略游戏

static void dfs(int u, int p){
dp[u][0] = 0;
dp[u][1] = 1;
for (int v : g[u]){
    if (v == p) continue;
        dfs(v, u);
        dp[u][0] += dp[v][1];
        dp[u][1] += min(dp[v][1], dp[v][0]);
    }
}