GabWiki | GabWiki

动态规划

0-1背包问题

以下代码中均用 n 代表物品种类， c 代表背包容量（capacity）， v 代表物品体积（volume）， w 代表物品价值（worth）， s 代表物品种类。

模板代码

Java

int n, c;
// 体积输入至v[1...n]  价值输入至w[1...n]
int[] v = new int[n + 1], w = new int[n + 1];
int[][] f = new int[n + 1][c + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= c; ++j) {
        f[i][j] = f[i - 1][j];
        if (v[i] <= j) f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}

// ans: f[n][c]

int n, c;
// 体积输入至v[1...n]  价值输入至w[1...n]
int[] v = new int[n + 1], w = new int[n + 1];
int[][] f = new int[n + 1][c + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= c; ++j) {
        f[i][j] = f[i - 1][j];
        if (v[i] <= j) f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i]] + w[i]);
    }
}

// ans: f[n][c]

一维数组优化

Java

int n, c;
// 体积输入至v[0...n-1]  价值输入至w[0...n-1]
int[] v = new int[n], w = new int[n];
int[] f = new int[c + 1];

for (int i = 0; i < n; ++i) {
    for (int j = c; j >= v[i]; --j) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

// ans: f[c]

int n, c;
// 体积输入至v[0...n-1]  价值输入至w[0...n-1]
int[] v = new int[n], w = new int[n];
int[] f = new int[c + 1];

for (int i = 0; i < n; ++i) {
    for (int j = c; j >= v[i]; --j) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

// ans: f[c]

完全背包问题

模板代码

Java

int n, c;
// 体积输入至v[1...n]  价值输入至w[1...n]
int[] v = new int[n + 1], w = new int[n + 1];
int[][] f = new int[n + 1][c + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= c; ++j) {
        for (int k = 0; k * v[i] <= j; ++k) {
            f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
}

// ans: f[n][c]

int n, c;
// 体积输入至v[1...n]  价值输入至w[1...n]
int[] v = new int[n + 1], w = new int[n + 1];
int[][] f = new int[n + 1][c + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= c; ++j) {
        for (int k = 0; k * v[i] <= j; ++k) {
            f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
}

// ans: f[n][c]

一维数组优化

Java

int n, c;
// 体积输入至v[0...n-1]  价值输入至w[0...n-1]
int[] v = new int[n], w = new int[n];
int[] f = new int[c + 1];

for (int i = 0; i < n; ++i) {
    for (int j = v[i]; j <= c; ++j) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

// ans: f[c]

int n, c;
// 体积输入至v[0...n-1]  价值输入至w[0...n-1]
int[] v = new int[n], w = new int[n];
int[] f = new int[c + 1];

for (int i = 0; i < n; ++i) {
    for (int j = v[i]; j <= c; ++j) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

// ans: f[c]

多重背包问题

模板代码

朴素多重背包

Java

int n, c;
// 体积输入至v[1...n]  价值输入至w[1...n]  数量输入至s[1...n]
int[] v = new int[n + 1], w = new int[n + 1], s = new int[n + 1];
int[][] f = new int[n + 1][c + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= c; ++j) {
        f[i][j] = f[i - 1][j];
        for (int k = 0; k * v[i] <= j && k <= s[i]; ++k) {
            f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
}

// ans: f[n][c]

int n, c;
// 体积输入至v[1...n]  价值输入至w[1...n]  数量输入至s[1...n]
int[] v = new int[n + 1], w = new int[n + 1], s = new int[n + 1];
int[][] f = new int[n + 1][c + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 0; j <= c; ++j) {
        f[i][j] = f[i - 1][j];
        for (int k = 0; k * v[i] <= j && k <= s[i]; ++k) {
            f[i][j] = Math.max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
}

// ans: f[n][c]

二进制优化+01背包一维优化

Java

// N: 最大物品种类  S: 单个物品的最大数量
static final int N, S;
// M = N * ⌈log_2{S}⌉
static final int M = (int) (N * Math.ceil(Math.log(S) / Math.log(2)));
int n, c;
int v = new int[M], w = new int[M];
int cnt = 0;

// 输入处理
for (int i = 0; i < n; ++i) {
    // 输入每个物品的体积, 价值, 最大数量
    int vi, wi, si;
    for (int x = 1; x <= si; ++cnt, si -= x, x <<= 1) {
        v[cnt] = x * vi;
        w[cnt] = x * wi;
    }
    if (si > 0) {
        v[cnt] = vi * si;
        w[cnt] = wi * si;
        ++cnt;
    }
}
n = cnt;
int[] f = new int[c + 1];

// 01背包一维优化
for (int i = 0; i < n; ++i) {
    for (int j = c; j >= v[i]; --j) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

// ans: f[c]

// N: 最大物品种类  S: 单个物品的最大数量
static final int N, S;
// M = N * ⌈log_2{S}⌉
static final int M = (int) (N * Math.ceil(Math.log(S) / Math.log(2)));
int n, c;
int v = new int[M], w = new int[M];
int cnt = 0;

// 输入处理
for (int i = 0; i < n; ++i) {
    // 输入每个物品的体积, 价值, 最大数量
    int vi, wi, si;
    for (int x = 1; x <= si; ++cnt, si -= x, x <<= 1) {
        v[cnt] = x * vi;
        w[cnt] = x * wi;
    }
    if (si > 0) {
        v[cnt] = vi * si;
        w[cnt] = wi * si;
        ++cnt;
    }
}
n = cnt;
int[] f = new int[c + 1];

// 01背包一维优化
for (int i = 0; i < n; ++i) {
    for (int j = c; j >= v[i]; --j) {
        f[j] = Math.max(f[j], f[j - v[i]] + w[i]);
    }
}

// ans: f[c]

单调队列优化+拷贝数组优化

Java

int n, c;
int[] f = new int[c + 1], g;
int[] que = new int[c + 1];
int hh, tt;
for (int i = 0; i < n; ++i) {
    // 输入每个物品的体积, 价值, 最大数量
    int v, w, s;
    g = f.clone(); // 拷贝上一层状态
    // 枚举余数
    for (int r = 0; r < v; ++r) {
        hh = 0; tt = -1; // 清空优先队列
        // 从余数开始枚举空间
        for (int j = r; j <= c; j += v) {
            // 将超出窗口范围的元素出队(`j - que[hh] / v`表示滑动窗口中的元素数量)
            while (hh <= tt && (j - que[hh]) / v > s) ++hh;
            // 当前状态比队尾元素表示的状态更优 队尾元素没有存在必要 队尾出队
            // 注意: 队尾元素需要加上价值偏移量: `(j - que[tt]) / v * w`
            while (hh <= tt && g[j] > g[que[tt]] + (j - que[tt]) / v * w) --tt;
            // 当前下标入队
            que[++tt] = j;
            // 更新当前这一层的状态(注意依旧要加上价值偏移量)
            f[j] = g[que[hh]] + (j - que[hh]) / v * w;
        }
    }
}

// ans: f[c]

int n, c;
int[] f = new int[c + 1], g;
int[] que = new int[c + 1];
int hh, tt;
for (int i = 0; i < n; ++i) {
    // 输入每个物品的体积, 价值, 最大数量
    int v, w, s;
    g = f.clone(); // 拷贝上一层状态
    // 枚举余数
    for (int r = 0; r < v; ++r) {
        hh = 0; tt = -1; // 清空优先队列
        // 从余数开始枚举空间
        for (int j = r; j <= c; j += v) {
            // 将超出窗口范围的元素出队(`j - que[hh] / v`表示滑动窗口中的元素数量)
            while (hh <= tt && (j - que[hh]) / v > s) ++hh;
            // 当前状态比队尾元素表示的状态更优 队尾元素没有存在必要 队尾出队
            // 注意: 队尾元素需要加上价值偏移量: `(j - que[tt]) / v * w`
            while (hh <= tt && g[j] > g[que[tt]] + (j - que[tt]) / v * w) --tt;
            // 当前下标入队
            que[++tt] = j;
            // 更新当前这一层的状态(注意依旧要加上价值偏移量)
            f[j] = g[que[hh]] + (j - que[hh]) / v * w;
        }
    }
}

// ans: f[c]

分组背包问题

优化后模板

Java

static final int S; // 单个物品的最大数量
int n, c;
// 数量输入至s[0...n]
int[] s = new int[n];
// 体积输入至v[0...n-1][0...s[i]-1]  价值输入至w[0...n-1][0...s[i]-1] 
int[][] v = new int[n][S], w = new int[n][S];
int[] f = new int[c + 1];

for (int i = 0; i < n; ++i) {
    for (int j = c; j >= 0; --j) {
        for (int k = 0; k < s[i]; ++k) {
            if (v[i][k] <= j) f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
        }
    }
}

// ans: f[c]

static final int S; // 单个物品的最大数量
int n, c;
// 数量输入至s[0...n]
int[] s = new int[n];
// 体积输入至v[0...n-1][0...s[i]-1]  价值输入至w[0...n-1][0...s[i]-1] 
int[][] v = new int[n][S], w = new int[n][S];
int[] f = new int[c + 1];

for (int i = 0; i < n; ++i) {
    for (int j = c; j >= 0; --j) {
        for (int k = 0; k < s[i]; ++k) {
            if (v[i][k] <= j) f[j] = Math.max(f[j], f[j - v[i][k]] + w[i][k]);
        }
    }
}

// ans: f[c]

最长上升子序列(LIS)

时间复杂度： $O (n^{2})$

C++

// 序列长度为n  序列输入至a[0...n-1]
int a[N], f[N], mx;

for (int i = 0; i < n; ++i) {
    f[i] = 1;
    for (int j = 0; j < i; ++j) {
        if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }
    mx = max(mx, f[i]);
}

// ans: mx

// 序列长度为n  序列输入至a[0...n-1]
int a[N], f[N], mx;

for (int i = 0; i < n; ++i) {
    f[i] = 1;
    for (int j = 0; j < i; ++j) {
        if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
    }
    mx = max(mx, f[i]);
}

// ans: mx

贪心优化

时间复杂度： $O (n \log n)$

C++

// 序列长度为n  序列输入至a[0...n-1]
int a[N], b[N], len = 0;

for (int i = 0; i < n; ++i) {
    if (b[len] < a[i]) b[++len] = a[i];
    else {
        int j = lower_bound(b, b + len, a[i]) - b;
        b[j] = a[i];
    }
}

// ans: len

// 序列长度为n  序列输入至a[0...n-1]
int a[N], b[N], len = 0;

for (int i = 0; i < n; ++i) {
    if (b[len] < a[i]) b[++len] = a[i];
    else {
        int j = lower_bound(b, b + len, a[i]) - b;
        b[j] = a[i];
    }
}

// ans: len

最长相同子序列(LCS)

JavaC++

Java

// 两字符串序列长度分别为n, m  输入至a[1...n], b[1...m]
int n, m;
char[] a, b;
int[][] f = new int[n + 1][m + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
    }
}

// ans: f[n][m]

// 两字符串序列长度分别为n, m  输入至a[1...n], b[1...m]
int n, m;
char[] a, b;
int[][] f = new int[n + 1][m + 1];

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
    }
}

// ans: f[n][m]

C++

// 两字符串序列长度分别为n, m  输入至a[1...n], b[1...m]
int n, m;
int a[N], b[N];
int f[N][N];

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    }
}

// ans: f[n][m]

// 两字符串序列长度分别为n, m  输入至a[1...n], b[1...m]
int n, m;
int a[N], b[N];
int f[N][N];

for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
        if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
        else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
    }
}

// ans: f[n][m]

数位DP

记忆化搜索模板（不考虑前导零）

C++

const int N, K, R;
int len, digits[N];
int f[N][K];

int dfs(int pos, int info, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && f[pos][info] != -1) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    for (int d = /* 下界 */; d <= up; ++d) {
        res += dfs(pos - 1, /* 信息 */, lim && d == digits[pos]);
    }
    return lim ? res : f[pos][info] = res;
}

int count(int n) {
    for (len = 0; n; n /= R) digits[len++] = n % R;
    memset(f, -1, sizeof(f));
    return dfs(len - 1, /* 信息 */, true);
}

const int N, K, R;
int len, digits[N];
int f[N][K];

int dfs(int pos, int info, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && f[pos][info] != -1) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    for (int d = /* 下界 */; d <= up; ++d) {
        res += dfs(pos - 1, /* 信息 */, lim && d == digits[pos]);
    }
    return lim ? res : f[pos][info] = res;
}

int count(int n) {
    for (len = 0; n; n /= R) digits[len++] = n % R;
    memset(f, -1, sizeof(f));
    return dfs(len - 1, /* 信息 */, true);
}

带注释模板

C++

// N为数据范围在需要考虑的进制下的最大位数 比如: 
//  - int范围内10进制最大9位 N就可以赋15
//  - int范围内2进制最大31位 N可以赋35
// K为需要携带的数字信息的最大数 比如:
//  - 携带的信息是10进制下的数上一位(0~9) K就可以赋15
//  - 携带的信息是2进制下的数中数位为1的数量(0~31) K就可以赋35
// R为需要考虑的进制系统(一般为2进制或10进制)
const int N, K, R;
int len, digits[N];
int f[N][K];

// pos: 当前枚举到的位  info: 携带的数字信息  lim: 之前的每一位数是否都到达了上界(n里的该数位)
int dfs(int pos, int info, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && f[pos][info] != -1) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    // 枚举当前位上可以填的数字 下界根据题目情况来定
    for (int d = /* 下界 */; d <= up; ++d) {
        // 这一行可以判断非法条件并根据情况continue
        res += dfs(pos - 1, /* 信息 */, lim && d == digits[pos]); // 递归处理下一位
    }
    // 该位未到达上界时 在返回的同时写入记忆数组
    return lim ? res : f[pos][info] = res;
}

int count(int n) {
    len = 0;
    // 预处理n在R进制下的每一位 记录在digits[0...len-1]中
    while (n) {
        digits[len++] = n % R;
        n /= R;
    }
    memset(f, -1, sizeof(f)); // 初始化记忆数组
    return dfs(len - 1, /* 信息 */, true);
}

// N为数据范围在需要考虑的进制下的最大位数 比如: 
//  - int范围内10进制最大9位 N就可以赋15
//  - int范围内2进制最大31位 N可以赋35
// K为需要携带的数字信息的最大数 比如:
//  - 携带的信息是10进制下的数上一位(0~9) K就可以赋15
//  - 携带的信息是2进制下的数中数位为1的数量(0~31) K就可以赋35
// R为需要考虑的进制系统(一般为2进制或10进制)
const int N, K, R;
int len, digits[N];
int f[N][K];

// pos: 当前枚举到的位  info: 携带的数字信息  lim: 之前的每一位数是否都到达了上界(n里的该数位)
int dfs(int pos, int info, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && f[pos][info] != -1) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    // 枚举当前位上可以填的数字 下界根据题目情况来定
    for (int d = /* 下界 */; d <= up; ++d) {
        // 这一行可以判断非法条件并根据情况continue
        res += dfs(pos - 1, /* 信息 */, lim && d == digits[pos]); // 递归处理下一位
    }
    // 该位未到达上界时 在返回的同时写入记忆数组
    return lim ? res : f[pos][info] = res;
}

int count(int n) {
    len = 0;
    // 预处理n在R进制下的每一位 记录在digits[0...len-1]中
    while (n) {
        digits[len++] = n % R;
        n /= R;
    }
    memset(f, -1, sizeof(f)); // 初始化记忆数组
    return dfs(len - 1, /* 信息 */, true);
}

记忆化搜索模板（考虑前导零）

C++

const int N, K, R;
int len, digits[N];
int f[N][K];

int dfs(int pos, int info, bool lead, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && !lead && ~f[pos][info]) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    for (int d = /* 下界 */; d <= up; ++d) {
        bool lead_zero = lead && !d;
        res += dfs(pos - 1, /* 信息 */, lead_zero, lim && d == digits[pos]);
    }
    return lim || lead ? res : f[pos][info] = res;
}

int count(int n) {
    for (len = 0; n; n /= R) digits[len++] = n % R;
    memset(f, -1, sizeof(f));
    return dfs(len - 1, /* 信息 */, true, true);
}

const int N, K, R;
int len, digits[N];
int f[N][K];

int dfs(int pos, int info, bool lead, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && !lead && ~f[pos][info]) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    for (int d = /* 下界 */; d <= up; ++d) {
        bool lead_zero = lead && !d;
        res += dfs(pos - 1, /* 信息 */, lead_zero, lim && d == digits[pos]);
    }
    return lim || lead ? res : f[pos][info] = res;
}

int count(int n) {
    for (len = 0; n; n /= R) digits[len++] = n % R;
    memset(f, -1, sizeof(f));
    return dfs(len - 1, /* 信息 */, true, true);
}

带注释模板

C++

// N为数据范围在需要考虑的进制下的最大位数 比如: 
//  - int范围内10进制最大9位 N就可以赋15
//  - int范围内2进制最大31位 N可以赋35
// K为需要携带的数字信息的最大数 比如:
//  - 携带的信息是10进制下的数上一位(0~9) K就可以赋15
//  - 携带的信息是2进制下的数中数位为1的数量(0~31) K就可以赋35
// R为需要考虑的进制系统(一般为2进制或10进制)
const int N, K, R;
int len, digits[N];
int f[N][K];

// pos: 当前枚举到的位  info: 携带的数字信息
// lead: 上一位是否为前导零  lim: 之前的每一位数是否都到达了上界(n里的该数位)
int dfs(int pos, int info, bool lead, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && !lead && ~f[pos][info]) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    // 枚举当前位上可以填的数字 下界根据题目情况来定
    for (int d = /* 下界 */; d <= up; ++d) {
        // 这一行可以判断非法条件并根据情况continue
        bool lead_zero = lead && !d; // 判断该位是否为前导零
        res += dfs(pos - 1, /* 信息 */, lead_zero, lim && d == digits[pos]);
    }
    // 该位未到达上界时 在返回的同时写入记忆数组
    return lim || lead ? res : f[pos][info] = res;
}

int count(int n) {
    // 预处理n在R进制下的每一位 记录在digits[0...len-1]中
    for (len = 0; n; n /= R) digits[len++] = n % R;
    memset(f, -1, sizeof(f)); // 初始化记忆数组
    return dfs(len - 1, /* 信息 */, true, true);
}

// N为数据范围在需要考虑的进制下的最大位数 比如: 
//  - int范围内10进制最大9位 N就可以赋15
//  - int范围内2进制最大31位 N可以赋35
// K为需要携带的数字信息的最大数 比如:
//  - 携带的信息是10进制下的数上一位(0~9) K就可以赋15
//  - 携带的信息是2进制下的数中数位为1的数量(0~31) K就可以赋35
// R为需要考虑的进制系统(一般为2进制或10进制)
const int N, K, R;
int len, digits[N];
int f[N][K];

// pos: 当前枚举到的位  info: 携带的数字信息
// lead: 上一位是否为前导零  lim: 之前的每一位数是否都到达了上界(n里的该数位)
int dfs(int pos, int info, bool lead, bool lim) {
    if (pos < 0) // 递归出口
    if (!lim && !lead && ~f[pos][info]) return f[pos][info];
    int res = 0, up = lim ? digits[pos] : /* 无限制时该位能填的最大数 */;
    // 枚举当前位上可以填的数字 下界根据题目情况来定
    for (int d = /* 下界 */; d <= up; ++d) {
        // 这一行可以判断非法条件并根据情况continue
        bool lead_zero = lead && !d; // 判断该位是否为前导零
        res += dfs(pos - 1, /* 信息 */, lead_zero, lim && d == digits[pos]);
    }
    // 该位未到达上界时 在返回的同时写入记忆数组
    return lim || lead ? res : f[pos][info] = res;
}

int count(int n) {
    // 预处理n在R进制下的每一位 记录在digits[0...len-1]中
    for (len = 0; n; n /= R) digits[len++] = n % R;
    memset(f, -1, sizeof(f)); // 初始化记忆数组
    return dfs(len - 1, /* 信息 */, true, true);
}

动态规划 ​

模板代码 ​

一维数组优化 ​

模板代码 ​

一维数组优化 ​

模板代码 ​

优化后模板 ​

数位DP ​

记忆化搜索模板（不考虑前导零） ​

带注释模板 ​

记忆化搜索模板（考虑前导零） ​

带注释模板 ​

动态规划

模板代码

一维数组优化

模板代码

一维数组优化

模板代码

优化后模板

数位DP

记忆化搜索模板（不考虑前导零）

带注释模板

记忆化搜索模板（考虑前导零）

带注释模板