线性DP:

最长单调子序列：

以最最长递增子序列为例：

说明：输出最长递增子序列的长度，递增子序列为数组中单调递增的元素的最大个数，元素不必相邻，但相对位置必须一致

import java.util.Scanner;
​
public class Main {
    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = sc.nextInt();
        }
​
        //计算
        for (int i = 0; i < n; i++) {
            arr[i][1] = 1;
            for (int j = 0; j < i; j++) {
                if(arr[i][0] > arr[j][0]){
                    arr[i][1] = Math.max(arr[i][1], arr[j][1]+1); //赋值比当前元素小的前一个元素的长度+1与1之间的最大值
                }
            }
        }
​
        //获取最大递增子序列长度
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, arr[i][1]);
        }
        //输出
        System.out.println(max);
        
    }
}

最大连续子序列和：

import java.util.Scanner;
​
//最大连续子序列和
//测试用例 -2,11,-4,13,-5,-2
public class study05 {
    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(",");
        int[] a = new int[s.length+1];
        a[0] = 0;
        for(int i=1;i<=s.length;i++){
            a[i] = Integer.parseInt(s[i-1]);
        }
​
        //计算
        int[] dp = new int[a.length];
        for(int i=1;i<s.length;i++){
            dp[i] = 0;
            //转移方程
            dp[i] = Math.max(dp[i]+a[i],a[i]);
        }
​
        //输出
        int max = 0;
        for(int i=1;i<a.length;i++){
            if(dp[i]>max){
                max = dp[i];
            }
        }
        System.out.println(max);
    }
}

最长公共子序列：(双序列)（二维dp）

import java.util.Scanner;
​
//最长公共子序列
//测试用例 BDCABC ABCBDAB 
public class Main {
    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        String[] s1 = sc.nextLine().split("");
        String[] s2 = sc.nextLine().split("");
        int[][] arr = new int[s1.length+1][s2.length+1];
        //计算
        for(int i=1;i<arr.length;i++){
            for(int j=1;j<arr[i].length;j++){
                //转移方程
                if(s1[i-1].equals(s2[j-1])){
                    arr[i][j] = arr[i-1][j-1]+1;
                }else {
                    arr[i][j] = Math.max(arr[i-1][j], arr[i][j-1]);
                }
            }
        }
        //输出
        System.out.println(arr[arr.length-1][arr[0].length-1]);
    }
}

背包DP：

01背包：

//01背包
public class Main {
    public static void main(String[] args) {
        //输入
        int[] w = {2,3,4}; //物品重量
        int[] v = {3,5,6}; //物品价值
        int n = 6; //背包容量
​
        int[][] arr = new int[w.length+1][n+1];
​
        //计算
        for (int i = 1; i < w.length+1; i++) {
            for (int j = 1; j < n+1; j++) {
                //转移方程
                if (j<w[i-1]) {
                    arr[i][j]=arr[i-1][j];
                }else{
                    arr[i][j]=Math.max(arr[i-1][j],arr[i-1][j-w[i-1]]+v[i-1]);
                }
            }
        }
​
        //输出
        System.out.println(arr[w.length][n]);
    }
}

完全背包：

//完全背包
public class Main {
    public static void main(String[] args) {
        //输入
        int[] w = {2,3,4}; //物品重量
        int[] v = {3,5,6}; //物品价值
        int n = 6; //背包容量
​
        int[][] arr = new int[w.length+1][n+1];
​
        //计算
        for (int i = 1; i < w.length+1; i++) {
            for (int j = 1; j < n+1; j++) {
                //转移方程
                if (j<w[i-1]) {
                    arr[i][j]=arr[i-1][j];
                }else{
                    arr[i][j]=Math.max(arr[i-1][j],arr[i][j-w[i-1]]+v[i-1]);
                }
            }
        }
​
        //输出
        System.out.println(arr[w.length][n]);
    }
}