Krains's Blog

vuePress-theme-reco Krains    2020 - 2021
Krains's Blog Krains's Blog

Choose mode

  • dark
  • auto
  • light
Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)
author-avatar

Krains

80

Article

22

Tag

Home
Category
  • Algorithm
  • LeetCode题解
  • 数据结构
  • 计算机基础知识
  • Java基础
  • Java多线程
  • JVM
  • MySQL
  • 设计模式
Tag
TimeLine
Contact
  • GitHub (opens new window)

动态规划

vuePress-theme-reco Krains    2020 - 2021

动态规划


Krains 2020-07-23 11:13:13

# 动态规划

  • 背包问题
  • 线性DP
  • 区间DP
  • 计数类DP
  • 数位统计DP
  • 状态压缩DP
  • 树形DP
  • 记忆化搜索

# DP问题分析

状态表示

  • 集合:每个状态表示一个集合
  • 属性:集合会落实到某个属性上,这个属性可能是最大值、最小值、数量等。

状态计算/集合划分:将集合划分,这些集合在已经在之前的计算中已经计算过了。

划分原则:不重合(非必要)、不漏(必要)。

# 背包问题

# 01背包

# 题目链接 (opens new window)

状态表示

  • 集合:定义状态(i, j)表示在前i个物品中选择物品体积之和小于等于j的所有选法的集合。
  • 属性:f(i,j)f(i, j)f(i,j)表示在这个集合(也就是所有选法)中物品价值之和的最大值。

状态计算:划分为两个集合

  • 不选第i件物品时:则状态就可以表示成在前i-1个物品中选择物品体积之和小于等于j的所有选法的集合,即f(i,j)=f(i−1,j)f(i, j) = f(i-1, j)f(i,j)=f(i−1,j)。
  • 选择第i件物品时:物品i必选,先不考虑物品i,状态就可以变成在前i-1个物品中选择物品体积之和小于等于j-v[i]的所有选法的集合,即f(i,j)=f(i−1,j−v[i])+w[i]f(i, j) = f(i-1, j - v[i]) + w[i]f(i,j)=f(i−1,j−v[i])+w[i]。

结合两种情况,取两者的最大值:

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i])f(i, j) =MAX(f(i-1, j),f(i-1,j-v[i])+w[i]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i])

朴素版:

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];

        for(int i = 1; i <= n; i++){
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }

        // 从1开始,初始dp[0][j]=0,方便dp[i-1][j]不存在问题
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= m; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= v[i])
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
            }
        }

        System.out.println(dp[n][m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

优化版:

需要注意两点

  • 为了保证选择物品i的时候使用的是i-1的状态,需要倒序v更新dp。
  • 可以省去dp[i][j]=dp[i-1][j],同时循环条件范围可以在[v[i], V]中,但是在朴素法中则不能这么做,因为要考虑取dp[i-1][j]的情况。
class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];

        for(int i = 1; i <= n; i++){
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }

        int[] dp = new int[m+1];
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= v[i]; j--){
                    dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
            }
        }

        System.out.println(dp[m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 完全背包

# 题目链接 (opens new window)

状态表示和01背包一样

状态计算,可以划分为k+1个集合,k是能够选择i物品的最大数量

选择k件物品i时,所产生的最大收益为,k属于[0,V/v[i]]

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])f(i, j)=MAX(f(i-1, j), f(i-1,j-v[i])+w[i],...,f(i-1, j-k*v[i])+k*w[i]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])

可以化简

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])f(i, j)=MAX(f(i-1, j), f(i-1,j-v[i])+w[i],...,f(i-1, j-k*v[i])+k*w[i]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])

f(i,j−v[i])=MAX(f(i−1,j−v[i]),...,f(i−1,j−k∗v[i])+(k−1)∗w[i])\ \ \ \ \ \ \ \ \ \ f(i, j-v[i])=MAX(f(i-1,j-v[i]),...,f(i-1, j-k*v[i])+(k-1)*w[i]) f(i,j−v[i])=MAX(f(i−1,j−v[i]),...,f(i−1,j−k∗v[i])+(k−1)∗w[i])

忽略f(i,j)f(i, j)f(i,j)中的第一项,我们可以将f(i,j)f(i, j)f(i,j)后面的项和f(i,j−v[i])f(i, j-v[i])f(i,j−v[i])一一对应,每一项f(i, j)要比它多一个w[i],因此,状态转移可以化简为:

f(i,j)=MAX(f(i−1,j),f(i,j−v[i])+w[i])f(i, j) = MAX(f(i-1, j),f(i,j-v[i])+w[i]) f(i,j)=MAX(f(i−1,j),f(i,j−v[i])+w[i])

对比01背包的方程:

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i])f(i, j) =MAX(f(i-1, j),f(i-1,j-v[i])+w[i]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i])

两者非常相似。可写出代码,由于f(i,j)f(i, j)f(i,j)第二项依赖于当前i,因此写优化版代码时无需倒序v。

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];

        for(int i = 1; i <= n; i++){
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }

        int[] dp = new int[m+1];
        for(int i = 1; i <= n; i++){
            for(int j = v[i]; j <= m; j++){
                    dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
            }
        }

        System.out.println(dp[m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 多重完全背包

# 题目链接 (opens new window)

状态表示和状态计算和完全背包类似,只是选取物品的件数有限制

状态计算:k属于[0, s[i]]

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])f(i, j)=MAX(f(i-1, j), f(i-1,j-v[i])+w[i],...,f(i-1, j-k*v[i])+k*w[i]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])

我们可以使用朴素版直接写出代码,但是有些题参数较大,需要进行优化。

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        int[] s = new int[n+1];

        for(int i = 1; i <= n; i++){
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
            s[i] = scanner.nextInt();
        }

        int[] dp = new int[m+1];
        for(int i = 1; i <= n; i++)
            // 因为依赖于i-1,需要倒着计算
            for(int j = m; j >= 0; j--)
                for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
                    dp[j] = Math.max(dp[j], dp[j-k * v[i]] + k * w[i]);

        System.out.println(dp[m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

尝试化简

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])f(i, j)=MAX(f(i-1, j), f(i-1,j-v[i])+w[i],...,f(i-1, j-k*v[i])+k*w[i]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i])+w[i],...,f(i−1,j−k∗v[i])+k∗w[i])

f(i,j−v[i])=MAX(f(i−1,j−v[i]),...,f(i−1,j−k∗v[i])+(k−1)∗w[i]+f(i−1,(k+1)∗v[i])+k∗w[i])\ \ \ \ \ \ \ \ \ \ f(i, j-v[i])=MAX(f(i-1,j-v[i]),...,f(i-1, j-k*v[i])+(k-1)*w[i]+f(i-1,(k+1)*v[i])+k*w[i]) f(i,j−v[i])=MAX(f(i−1,j−v[i]),...,f(i−1,j−k∗v[i])+(k−1)∗w[i]+f(i−1,(k+1)∗v[i])+k∗w[i])

对比完全背包的优化,这里多了最后一项,因此无法像完全背包一样优化。

我们考虑这样一个问题

对于数字15,我们可以用1,2,4,8这4个数的组合表示0-15的任何一个数

对于数字17,可以用1,2,4,8,2这5个数的组合来表示0-17的中任何一个数

按照上面的问题,我们可以将物品i打包,打包后成为一个新物品,而这些打包的物品的组合可以拼凑出所有的s[i],对于每件打包的新物品只可以选1件或者不选,这样问题就转化成01背包问题了。

对于s[i]件物品,可以拆分成log2s[i]log_2s[i]log2​s[i]件物品,因此拆分所有的物品,最后的物品数量为O(N∗log2S)O(N*log_2S)O(N∗log2​S),算法的时间复杂度为O(N∗V∗log2S)O(N * V * log_2S)O(N∗V∗log2​S)

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int N = 12500; // 打包后物品数量可能为1000*log2000 约等于12000
        int[] v = new int[N];
        int[] w = new int[N];

        int cnt = 1;
        for(int i = 1; i <= n; i++){
            int vt = scanner.nextInt();
            int wt = scanner.nextInt();
            int st = scanner.nextInt();

            int k = 1;
            // 将每件物品打包拆分
            while(k <= st){
                v[cnt] = k * vt;
                w[cnt] = k * wt;
                cnt++;
                st -= k;
                k *= 2;
            }
            if(st != 0){
                v[cnt] = st * vt;
                w[cnt] = st * wt;
                cnt++;
            }
        }

        // 01背包
        int[] dp = new int[m+1];
        for(int i = 1; i <= cnt; i++)
            for(int j = m; j >= v[i]; j--)
                dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);

        System.out.println(dp[m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# 分组背包

# 题目链接 (opens new window)

状态表示

  • 集合:状态(i,j)(i, j)(i,j)表示前i组内选择体积不超过j的选择的集合。
  • 属性:f(i,j)f(i, j)f(i,j)表示集合中某选择的价值最大值。

状态计算/集合划分,跟0,1背包类似

  • 不选i组的物品,f(i,j)=f(i−1,j)f(i, j) = f(i-1, j)f(i,j)=f(i−1,j)
  • 选择i组的第k件物品,f(i,j)=f(i−1,j−v[i][k])+w[i][k]f(i, j) = f(i-1, j-v[i][k])+w[i][k]f(i,j)=f(i−1,j−v[i][k])+w[i][k]

最后转移方程,k属于[1, s[i]],s[i]是i组的物品数量

f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i][k])+w[i][k])f(i, j)=MAX(f(i-1, j), f(i-1, j-v[i][k])+w[i][k]) f(i,j)=MAX(f(i−1,j),f(i−1,j−v[i][k])+w[i][k])

import java.util.Scanner;

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] v = new int[n+1][];
        int[][] w = new int[n+1][];
        int[] s = new int[n+1];

        for(int i = 1; i <= n; i++){
            s[i] = scanner.nextInt();
            v[i] = new int[s[i]+1];
            w[i] = new int[s[i]+1];
            for(int j = 1; j <= s[i]; j++){
                v[i][j] = scanner.nextInt();
                w[i][j] = scanner.nextInt();
            }
        }

        int[] dp = new int[m+1];    
        for(int i = 1; i <= n; i++)
            for(int j = m; j > 0; j--)
                for(int k = 0; k <= s[i]; k++)
                    // 注意if不能写在for循环里边
                    if(v[i][k] <= j)
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]);

        System.out.println(dp[m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

背包问题总结

  • 如果状态计算依赖与i-1,要倒序枚举V才能保证使用到的dp[j-v[i]]没有被更新过,表示是上一层的状态。
  • 如果使用状态方程涉及到i-1,多定义一行,如果涉及j-1,多定义一列,从1开始枚举行可以较好的处理边界问题。

# 线性DP

线性DP指在状态计算的时候是线性更新的,这类DP的状态一般依赖于左边(i-1)或者上边(j-1)的状态,因此这类DP一般比较容易想。

# 最长上升子序列

# 题目链接 (opens new window)

状态表示

  • 集合:(i)表示所有以a[i]结尾的上升子序列的集合
  • 属性:f(i)表示所有集合大小的最大值

状态计算/集合划分,可以使用当前最长上升序列中上一个元素是a[0-j]的其中一个来划分。得状态转移:

f(i)=Math.max(1,{f(j)+1∣j∈[0,i−1],a[j]<a[i]})f(i) = Math.max(1, \{f(j)+1|j\in[0,i-1],a[j]<a[i]\}) f(i)=Math.max(1,{f(j)+1∣j∈[0,i−1],a[j]<a[i]})

import java.util.Scanner;

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int[] dp = new int[n];
        int res = 0;
        for(int i = 0; i < n; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(a[j] < a[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }

        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 二分+贪心优化

长度为i的上升子序列有很多,我们只用贪心地保存其上升子序列中最小末尾的数。

使用dp[i]表示长度为i的上升子序列中序列最后一个最小数。

dp[i]是单调递增的,在将一个数a[i]放置在上升子序列中时,只需要查找a[i]在dp[i]的插入位置就好。

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 哨兵
        dp[0] = Integer.MIN_VALUE;
        int res = 0;
        for(int i = 0; i < n; i++){
            int left = 0;
            int right = res;
            while(left <= right){
                int mid = left + (right - left) / 2;
                if(dp[mid] < a[i]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
            res = Math.max(res, left);
            dp[left] = a[i];
        }

        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 最长公共子序列

# 题目链接 (opens new window)

状态表示

  • 集合:(i, j)表示a的前i个字符和b的前j个字符的所有公共子序列构成的集合。
  • 属性:f(i,j)f(i, j)f(i,j)表示所有子序列的最长公共子序列。

状态计算/集合划分

  • 不含a[i],不含b[j],f(i,j)=f(i−1,j−1)f(i, j) = f(i-1, j-1)f(i,j)=f(i−1,j−1)

  • 包含a[i],不含b[j],f(i,j)=f(i,j−1)f(i, j) = f(i, j-1)f(i,j)=f(i,j−1)

  • 不含a[i],包含b[j],f(i,j)=f(i−1,j)f(i, j) = f(i-1, j)f(i,j)=f(i−1,j)

  • 包含a[i],包含b[j],f(i,j)=f(i−1,j−1)+1f(i, j) = f(i-1, j-1)+1f(i,j)=f(i−1,j−1)+1

注意在集合划分中包含a[i], 不含b[j]中,这个被划分出来的集合应该是的前i个字符和b的前j-1个字符的所有公共子序列构成的集合,且a[i]一定在公共子序列中,但是f(i, j-1)表示a[i]可能在也可能不在,也就是说这两个集合不相等,但是f(i, j-1)是包含前一个集合的,求max的话集合重叠也不影响最值。

同理f(i-1, j)也是一样的。

f(i-1, j-1)是包含在f(i, j-1)中的,所以可以去掉这个转移。

最后分析可得状态转移

f(i,j)=max(f(i−1,j),f(i,j−1),f(i−1,j−1)+1)f(i, j) = max(f(i-1,j),f(i,j-1),f(i-1,j-1)+1) f(i,j)=max(f(i−1,j),f(i,j−1),f(i−1,j−1)+1)

import java.util.Arrays;
import java.util.Scanner;

class Main{

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String a = scanner.next();
        String b = scanner.next();

        int[][] dp = new int[a.length()+1][b.length()+1];
        for(int i = 1; i < dp.length; i++){
            for(int j = 1; j < dp[0].length; j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(a.charAt(i-1) == b.charAt(j-1))
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1] + 1);
            }
        }

        System.out.println(dp[a.length()][b.length()]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 最短编辑距离

# 题目链接 (opens new window)

状态表示

  • 集合:(i, j)表示A的前i个字符经过编辑得到B的前j个字符的操作的集合
  • 属性:f(i,j)f(i,j)f(i,j)表示所有操作的最少操作次数

状态计算/集合划分

以A的第i个字符所进行的操作进行划分

  • 删除:删除掉A的第i个字符,f(i,j)=f(i−1,j)+1f(i,j)=f(i-1,j)+1f(i,j)=f(i−1,j)+1
  • 增加:在A的i位置增加一个字符B[j],f(i,j)=f(i,j−1)+1f(i,j)=f(i,j-1)+1f(i,j)=f(i,j−1)+1
  • 替换:将A[i]字符替换成B[j],f(i,j)=f(i−1,j−1)+(A[i]==B[j]?0:1)f(i,j)=f(i-1,j-1)+(A[i]==B[j]?0:1)f(i,j)=f(i−1,j−1)+(A[i]==B[j]?0:1)

取三个操作的最小值即为f(i,j)f(i,j)f(i,j)。

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String A = scanner.next();
        int m = scanner.nextInt();
        String B = scanner.next();

        int[][] dp = new int[n+1][m+1];
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= m; j++){
                if(i == 0 && j == 0)
                    continue;
                if(i == 0){
                    dp[i][j] = j;
                }else if(j == 0){
                    dp[i][j] = i;
                }else {
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + 1;
                    dp[i][j] = Math.min(dp[i][j], dp[i-1][j-1] 
                            + (A.charAt(i-1) == B.charAt(j-1) ? 0 : 1));
                }
            }
        }

        System.out.println(dp[n][m]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 区间DP

# 石子合并

# 题目链接 (opens new window)

状态表示

  • 集合:(i,j)(i, j)(i,j)表示在区间[i, j]合并石子的所有方案的集合。
  • 属性:f(i,j)f(i,j)f(i,j)表示所有集合中某一种方案的最小体力值。

状态计算/集合划分

使用最后一次合并的分界点k来对集合进行划分,那么所花费体力为

f(i,k)+f(k+1,j)+sum(i,j)f(i,k)+f(k+1,j)+sum(i,j) f(i,k)+f(k+1,j)+sum(i,j)

即区间[i, k]合并成一堆的最小体力和区间[k+1, j]合并成一堆的最小体力加上这两堆合并在一起的体力值sum(i,j),sum(i,j)为区间[i,j]之间的石子重量。

所以取这些所有分界点最小值就是f(i,j)f(i, j)f(i,j):

f(i,j)=min(f(i,k)+f(k+1,j)+sum(i,j)),k∈[i,j−1]f(i,j)=min(f(i,k)+f(k+1,j)+sum(i,j)),k\in[i,j-1] f(i,j)=min(f(i,k)+f(k+1,j)+sum(i,j)),k∈[i,j−1]

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        int[] preSum = new int[n+1];
        int[][] dp = new int[n][n];

        for(int i = 0; i < n; i++){
            nums[i] = scanner.nextInt();
        }

        for(int i = 1; i <= n; i++){
            preSum[i] = preSum[i-1] + nums[i-1];
        }

        // 区间dp先枚举区间长度,再枚举起点
        for(int len = 2; len <= n; len++){
            for(int i = 0; i+len-1 < n; i++){
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for(int k = i; k < j; k++){
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k+1][j]+preSum[j+1]-preSum[i]);
                }
            }
        }
        
        System.out.println(dp[0][n-1]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 计数类DP

# 整数划分

# 记忆化

DFS加记忆化,由于相同划分的不同顺序算作一个序列,因此要多加一个维度,保证数字选择是不递减的,以避免重复选择的情况。

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(new Main().helper(n,1, new Integer[n+1][n+1]));
    }
    
	// Memo[i][j]表示从数字i开始选择,总和为j的方案总数
    public int helper(int n, int j, Integer[][] Memo){
        int mod = (int)1e9+7;
        if(Memo[n][j] != null)
            return Memo[n][j];
        if(n == 0)
            return 1;

        int count = 0;
        for(int i = j; i <= n; i++){
            count = (count + helper(n-i, i, Memo)) % mod;
        }

        return Memo[n][j] = count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 动态规划

# 类比完全背包

可以将n看做是一个容量为n的背包,从1-n中选择几个数,使得恰好装满这个背包的方案数。

状态表示

  • 集合:(i,j)(i,j)(i,j)表示从1-i中选择几个数恰好容量为j的所有方案的集合

  • 属性:集合中元素(方案)的数量

状态计算/集合划分

  • 选0个i
  • 选1个i
  • ...
  • 选k个i

两个方程

f(i,j)=f(i−1,j)+f(i−1,j−i)+f(i−1,j−2∗i)+...+f(i−1,j−k∗i)f(i,j)=f(i-1,j)+f(i-1,j-i)+f(i-1,j-2*i)+...+f(i-1,j-k*i) f(i,j)=f(i−1,j)+f(i−1,j−i)+f(i−1,j−2∗i)+...+f(i−1,j−k∗i)

f(i,j−i)=f(i−1,j−i)+f(i−1,j−2∗i)+...+f(i−1,j−k∗i)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f(i,j-i)=f(i-1,j-i)+f(i-1,j-2*i)+...+f(i-1,j-k*i) f(i,j−i)=f(i−1,j−i)+f(i−1,j−2∗i)+...+f(i−1,j−k∗i)

化简得

f(i,j)=f(i−1,j)+f(i,j−i)f(i,j)=f(i-1,j)+f(i,j-i) f(i,j)=f(i−1,j)+f(i,j−i)

代码:

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int mod = (int)1e9+7;
        int[] dp = new int[n+1];
        dp[0] = 1;

        // 先枚举物品,在枚举容量
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                dp[j] = (dp[j] + dp[j-i]) % mod;
            }
        }

        System.out.println(dp[n]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 另一种思路

状态表示

  • 集合:(i,j)(i,j)(i,j)表示使用j个数能够凑成总和为i的方案的集合
  • 属性:f(i,j)f(i,j)f(i,j)表示这些方案的数量

状态计算/集合划分

  • 使用j个数能够凑成i,这j个数中最小值为1的集合,去掉一个1,则状态变为:f(i,j)=f(i−1,j−1)f(i,j)=f(i-1,j-1)f(i,j)=f(i−1,j−1)
  • 使用j个数能够凑成i,这j个数中最小值不为1的集合,将这j个数都减去一个1,则状态变为:f(i,j)=f(i−j,j)f(i,j)=f(i-j,j)f(i,j)=f(i−j,j),此时状态表示为j个数能够凑成i-j的所有方案的数量。

将两个数量相加

f(i,j)=f(i−1,j−1)+f(i−j,j)f(i,j)=f(i-1,j-1)+f(i-j,j) f(i,j)=f(i−1,j−1)+f(i−j,j)

代码

class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int mod = (int)1e9+7;
        int[][] dp = new int[n+1][n+1];
        dp[0][0] = 1;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i][j] = (dp[i-1][j-1] + dp[i-j][j]) % mod;
            }
        }

        // 最后还要统计所有得到n的方案数
        int res = 0;
        for(int i = 1; i <= n; i++)
            res = (res + dp[n][i]) % mod;
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 动态规划
  • DP问题分析
  • 背包问题
  • 01背包
  • 完全背包
  • 多重完全背包
  • 分组背包
  • 线性DP
  • 最长上升子序列
  • 最长公共子序列
  • 最短编辑距离
  • 区间DP
  • 石子合并
  • 计数类DP
  • 整数划分