动态规划

acwing
算法
发布日期:   2023-06-19
更新日期:   2023-06-19
文章字数:   3.5k
阅读次数:  

背包问题

01背包问题

有 N 件物品和一个容量为 V的背包，每件物品有各自的价值且只能被选择一次，要求在有限的背包容量下，装入的物品总价值最大。

「0-1 背包」是较为简单的动态规划问题，也是其余背包问题的基础。

动态规划是不断决策求最优解的过程，「0-1 背包」即是不断对第 i个物品的做出决策，「0-1」正好代表不选与选两种决定。

例题

01背包

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

代码：

//朴素做法
import java.util.*;

public class Main{
    
    static int N = 1010, n, m;
    static int[] v = new int[N], w = new int[N];
    //考虑前 i个物品，背包容量 j下的最大价值
    static int[][] dp = new int[N][N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        
        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.print(dp[n][m]);
    }
}


//空间压缩优化
import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int[] v = new int[N], w = new int[N];
    //降维使用因为每次使用的是上一层的数据，所有我们不需要保存所有的数据，只需要上一层的数据。
    //可以理解dp[][]仍为2维，但是第一维长度为1.只有一层。保存上一层。
    static int[] dp = new int[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        
        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.print(dp[m]);
    }
}

完全背包问题

思路同01背包问题。区别在于01背包对于每种物品只有选或不选，这也即「01」的由来。多重背包则对于每种物品可以多次选择。

例题

完全背包

f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包

f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

代码：

//暴力 O(n3)
import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int[] v = new int[N], w = new int[N];
    static int[][] dp = new int[N][N]; //前i个物品，背包容量j下的最优解（最大价值）
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= m ; j++){
                int amount = j / v[i];  // j体积时物品最多能选的次数    
                for(int k = 0; k <= amount; k++) // 枚举选择第i个物品的个数
                    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
        System.out.print(dp[n][m]);
    }
}



//朴素 O(n2)
import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int[] v = new int[N], w = new int[N];
    static int[][] dp = new int[N][N]; //前i个物品，背包容量j下的最优解（最大价值）
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        
        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][j - v[i]] + w[i]);
                }
            }
        }
        System.out.print(dp[n][m]);
    }
}



//空间优化
import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int[] v = new int[N], w = new int[N]; 
    static int[] dp = new int[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        
        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.print(dp[m]);
    }
}

多重背包问题

例题

在完全背包中,通过两个状态转移方程：

$$
\begin{aligned}
f[i,j]&=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,f[i-1,j-3v]+3w,……)\
f[i,j-v]&=max(\qquad \qquad, f[i-1,j-v],f[i-1,j-2v]+w,f[i-1,j-3v]+2w,……)
\end{aligned}
$$
可以得到 f[i][j] = max(f[i - 1][j], f[i][j - v] + w)。

在多重背包通过两个状态转移方程
$$
\begin{aligned}
f[i,j]&=max(f[i-1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w,……,f[i-1,j-Sv]+Sw)\
f[i,j-v]&=max(\qquad \qquad, f[i-1,j-v],f[i-1,j-2v]+w,……,f[i-1,j-Sv]+(S-1)w,f[i-1,j-(S+1)v]+Sw)
\end{aligned}
$$
不能得到上述结论，因为多重背包方程比完全背包方程多出了一项，所以不能用完全背包的优化方式优化多重背包

那为什么完全背包不会有最后一项？

完全背包由于对每种物品没有选择个数的限制，所以只要体积够用就可以一直选，没有最后一项

我们可以考虑使用二进制的方法优化多重背包问题

二进制优化

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例：

10

代码：

//暴力做法
import java.util.*;

public class Main{
    static int N = 110, n, m;
    static int[] v = new int[N], w = new int[N], s = new int[N];
    static int[][] dp = new int[N][N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1 ; i <= n ; i ++ ){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
            s[i] = in.nextInt();
        }

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


        System.out.println(dp[n][m]);
    }
}


//二进制优化
import java.util.*;

public class Main{
    static int N = 12010, M = 2010, n, m;
    static int[] v = new int[N], w = new int[N]; 
    static int[] dp = new int[M];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            int s = in.nextInt();
            int k = 1;
            while(k < s){
                cnt++;
                v[cnt] = k * a;
                w[cnt] = k * b;
                s -= k;
                k *= 2;
            }
            if(s > 0){
                cnt++;
                v[cnt] = s * a;
                w[cnt] = s * b;
            }
        }
        
        n = cnt;
        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.print(dp[m]);
    }
}

分组背包问题

例题

分组背包

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例：

8

代码：

import java.util.*;

public class Main{
    static int N = 110, n, m;
    //v为体积，w为价值，s代表第i组物品的个数
    static int[][] v = new int[N][N], w = new int[N][N];
    static int[] s = new int[N];
    //只从前i组物品中选，当前体积小于等于j的最大值
    static int[] dp = new int[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        for(int i = 1; i <= n; i++){
            s[i] = in.nextInt();
            for(int j = 1; j <= s[i]; j++){
                v[i][j] = in.nextInt();
                w[i][j] = in.nextInt();
            }
        }
        
        for(int i = 1; i <= n; i++){
            for(int j = m; j >= 0; j--){
                for(int k = 1; k <= s[i]; k++){
                    if(v[i][k] <= j){
                        dp[j] = Math.max(dp[j], dp[j - v[i][k]] + w[i][k]); 
                    }
                }
            }
        }
        
        System.out.print(dp[m]);
    }
}

线性DP

数字三角形

例题

思路

输入样例：

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例：

30

代码：

import java.util.*;

public class Main{
    static int N = 510, n;
    static int[][] w = new int[N][N],  dp = new int[N][N]; 
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                w[i][j] = in.nextInt();
            }
        }
        
        for(int i = 1; i <= n; i++){
            dp[n][i] = w[n][i];
        }
        for(int i = n - 1; i > 0; i--){
            for(int j = 1; j <= i; j++){
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + w[i][j];
            }
        }
        
        System.out.print(dp[1][1]);
    }
}

最长上升子序列

例题

思路

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

代码：

import java.util.*;

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


//输出路径
import java.util.*;

public class Main{
    static int N = 1010, n;
    //g[i]表示以a[i]结尾的最长子序列的前一个字母的下标
    static int[] a = new int[N], dp = new int[N], g = new int[N], path = new int[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 1; i <= n; i++){
            a[i] = in.nextInt();
        }
        
        for(int i = 1; i <= n; i++){
            dp[i] = 1;
            //等于0表示只有一个数
            g[i] = 0;
            for(int j = 1; j < i; j++){
                if(a[j] < a[i]){
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        g[i] = j;
                    }
                }
            }
        }
        
        int len = 0;
        int k = 0;
        for(int i = 1; i <= n; i++){
            if(len < dp[i]){
                len = dp[i];
                k = i;
            }
        }
        
        System.out.println(len);
        
        int index = 1;
        while(g[k] != 0){
            path[index] =  a[k];
            k = g[k];
            index++;
        }
        
        path[index] = a[k];
        for(int i =  index; i > 1; i--){
            System.out.print(path[i] + "->");
        }
        System.out.print(path[1]);
       
    }
}

最长公共子序列

例题

思路

输入样例：

4 5
acbd
abedc

输出样例：

3

代码：

import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int[][] dp = new int[N][N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        in.nextLine();
        String a = in.nextLine();
        String b = in.nextLine();
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(a.charAt(i - 1) == b.charAt(j - 1)){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}

最短编辑距离

例题

思路

输入样例：

10 
AGTCTGACGC
11 
AGTAAGTAGGC

输出样例：

4

代码：

import java.util.*;

public class Main{
    static int N = 1010, n, m;
    static int[][] dp = new int[N][N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        String a = in.next();
        m = in.nextInt();
        String b = in.next();
        
        for(int i = 1; i <= n; i++){
            dp[i][0] = i;
        }
        for(int j = 1; j <= m; j++){
            dp[0][j] = j;
        }
       
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
               if(a.charAt(i - 1) == b.charAt(j - 1)){
                   dp[i][j] = dp[i - 1][j - 1];
               }else{
                   dp[i][j] =  dp[i - 1][j - 1] + 1;
                   dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1);
                   dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1);
               }
            }
        }
        System.out.println(dp[n][m]);
    }
}

区间DP

例题

思路：

思路

输入样例：

4
1 3 5 2

输出样例：

22

代码：

import java.util.*;

public class Main{
    static int N = 310, n;
    static int[] a = new int[N], s = new int[N];//前缀和
    static int[][] dp =new int[N][N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 1; i <= n; i++){
            a[i] = in.nextInt();
            s[i] = s[i-1] + a[i];
        }
        
        //所有的区间dp问题枚举时，
        //第一维通常是枚举区间长度，并且一般 len = 1 时用来初始化，枚举从 len = 2 开始；
        //第二维枚举起点 i （右端点 j 自动获得，j = i + len - 1）
        for(int len = 2; len <= n; len++){
            for(int i = 1; i + len - 1 <= n; i++){
                 int l = i, r = i + len - 1;
                 dp[l][r] = (int)1e9;
                 for(int k = l; k < r; k++){
                     dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
                 }
            }
        }
        System.out.println(dp[1][n]);       
    }
}

计数类DP

例题

思路：

思路

输入样例:

5

输出样例：

7

代码：

import java.util.*;

//完全背包解法
public class Main{
    static int N = 1010, mod = (int)1e9 + 7, n;
    //dp[i][j]表示只从1~i中选，且总和等于j的方案数
    static int[] dp = new int[N];
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = i; j <= n; j++){
                //dp[i][j] = dp[i - 1][j] + dp[i][j - i]
               dp[j] = (dp[j] + dp[j - i]) % mod;
            }
        }
        System.out.println(dp[n]);
    }
}

数位统计DP

状态压缩DP

题目

思路：

思路

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

代码：

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

/**
 * @author liuzhangjie
 * @date 2023/05/11
 */
public class Main {
    static int N = 20, M = 1 << N, n;
    static int[][] f = new int[M][N], w = new int[N][N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++){
                w[i][j] = in.nextInt();
            }
        }

        for(int i = 0 ; i < 1 << n ; i ++ )
            Arrays.fill(f[i],0x3f3f3f); //除了第一个点，其他点初始化成正无穷
        f[1][0] = 0;

        //枚举所有状态
        for (int i = 0; i < 1 << n; i++) {
            //枚举所有终点
            for (int j = 0; j < n; j++) {
                //表示能够走到j,才能进行下一步
                if(((i >> j) & 1) == 1){
                    //j是终点，k是倒数第二个点
                    for(int k = 0; k < n; k++){
                        //首先减掉最后一个点剩下的路径中要能够走到k才能够进行状态计算
                        if(((i >> k) & 1) == 1){
                            //0 - k - j的途径 f[state - (1 << j)][k] + w[k][j]
                            f[i][j] = Math.min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
                        }
                    }
                }
            }
        }

        System.out.println(f[(1 << n) - 1][n - 1]);
    }
}

树形DP

题目

思路：

输入样例：

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出样例：

5

代码：

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

/**
 * @author liuzhangjie
 * @date 2023/05/10
 */
public class Main {
    static int N = 6010, n, idx;
    static int[] e = new int[N], ne = new int[N], h = new int[N];
    static int[] w = new int[N];
    
    static boolean[] st = new boolean[N];//st[i]表示节点i是否有父节点
    static int[][] f = new int[N][2];//f[i][0]表示不选i节点的情况下，以i为根节点的子数的最大值，f[i][1]表示选i节点

    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++ ;
    }

    static void dfs(int u){
        f[u][1] = w[u];

        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            dfs(j);
            f[u][0] += Math.max(f[j][0], f[j][1]);
            f[u][1] += f[j][0];
        }
    }


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

        Arrays.fill(h, -1);
        for(int i = 0; i < n - 1; i++){
            int a = in.nextInt();
            int b = in.nextInt();
            add(b, a);
            st[a] = true;
        }
        int root = 1;
        while(st[root]){
            root++;
        }
        
        dfs(root);
        
        System.out.println(Math.max(f[root][0], f[root][1]));
    }
}
文章作者: liuzhangjie
文章链接: https://liuzhangjie1713.github.io/2023/06/19/dong-tai-gui-hua/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 liuzhangjie !
acwing
  目录