Java算法模板-DP

作者： 作者的头像   zyyyds ,  2024-04-10 21:23:07 ,  所有人可见 ,  阅读 10

0


线性DP

最长上升子序列

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1010, M = 41;
        static int[] a = new int [N];
        static int[] f = new int [N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            for(int i = 1; i <= n; i ++)
                a[i] = sc.nextInt();

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

            int res = -1;
            for(int i = 1; i <= n; i ++) res = Math.max(res, f[i]);

            System.out.println(res);
       }   
}

最长公共子序列

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1010, M = 41;
        static int[] a = new int [N];
        static int[][] f = new int [N][N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();
            String s1 = sc.next();
            String s2 = sc.next();
            char[] c1 = s1.toCharArray();
            char[] c2 = s2.toCharArray();

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

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

背包问题

01背包
未优化空间版本


import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1010;
        static int[][] dp = new int[N][N];
        static int[] v = new int[N];
        static int[] w = new int[N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();

            for(int i = 1; i <= n; i ++)
            {
                v[i] = sc.nextInt();
                w[i] = sc.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.println(dp[n][m]);
       }   
}

优化空间版本


import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1010;
        static int[] dp = new int[N];
        static int[] v = new int[N];
        static int[] w = new int[N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();

            for(int i = 1; i <= n; i ++)
            {
                v[i] = sc.nextInt();
                w[i] = sc.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.println(dp[m]);
       }   
}

完全背包
未优化空间版本


import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1010;
        static int[][] dp = new int[N][N];
        static int[] v = new int[N];
        static int[] w = new int[N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();

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

            for(int i = 1; i <= n; i ++)
                for(int j = 0; j <= m; j ++)
                    for(int k = 0; 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.*;
import java.io.*;
    public class Main {
        static final int N = 1010;
        static int[][] dp = new int[N][N];
        static int[] v = new int[N];
        static int[] w = new int[N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();

            for(int i = 1; i <= n; i ++)
            {
                v[i] = sc.nextInt();
                w[i] = sc.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.println(dp[n][m]);
       }   
}

优化空间版本


import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 1010;
        static int[] dp = new int[N];
        static int[] v = new int[N];
        static int[] w = new int[N];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();

            for(int i = 1; i <= n; i ++)
            {
                v[i] = sc.nextInt();
                w[i] = sc.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.println(dp[m]);
       }   
}

背包问题求方案数
根据递推关系优化表达式，进而优化时间复杂度
{72DA09D1-165E-41a5-A545-3C5F8CF32164}.png
不优化空间的写法：

import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 10010;
        static long[][] dp = new long[26][N];
        static int[] v = new int[26];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();
            for(int i = 1; i <= n; i ++)
            {
                v[i] = sc.nextInt();
            }
            dp[0][0] = 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] += dp[i][j - v[i]];
                }

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

优化空间的写法(和完全背包优化方法一样):


import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 10010;
        static long[] dp = new long[N];
        static int[] v = new int[26];
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            int m = sc.nextInt();
            for(int i = 1; i <= n; i ++)
            {
                v[i] = sc.nextInt();
            }
            dp[0] = 1;
            for(int i = 1; i <= n; i ++)
                for(int j = 0; j <= m; j ++)
                {
                    if(j >= v[i]) dp[j] += dp[j - v[i]];
                }

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

区间DP


import java.util.*;
import java.io.*;
    public class Main {
        static final int N = 310, MOD = (int)1e9 + 7; //b为设置的偏移量 
        static int[][] dp = new int[N][N];
        static int[] s = new int[N];


        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            //BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
            //BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            int n = sc.nextInt();
            for(int i = 1; i <= n; i ++)
            {
                int x = sc.nextInt();
                s[i] = s[i - 1] + x;
            }

            for(int len = 2; len <= n; len ++)
            {
                for(int i = 1; i + len - 1 <= n; i ++)
                {
                    int j = i + len - 1;
                    dp[i][j] = (int)1e9;
                    for(int k = i; k < j; k ++)
                    {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
                    }
                }
            }
            System.out.println(dp[1][n]);
       }   
}

计数类DP

0 评论