动态规划(DP)——线性DP

898. 数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
输入格式
第一行包含整数 n，表示数字三角形的层数。
接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。
输出格式
输出一个整数，表示最大的路径数字和。
数据范围
1≤n≤500,
−10000≤三角形中的整数≤10000
输入样例：
5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5
输出样例：
30

package luogu.dp.线性DP;
import java.io.*;
public class 数字三角形 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws IOException {
        int n = in();
        int[][] a = new int[n+1][n+1];
        for ( int i=1; i<=n; i++ ) {
            for ( int j=1; j<=i; j++ ) {
                a[i][j] = in();
            }
        }
        int[][] dp = new int[n+1][n+2];
        for ( int i=0; i<=n; i++ ) {
            for ( int j=0; j<=i+1; j++ ) {
//                用MIN会溢出，加负数会向负数溢出
//                dp[i][j] = Integer.MIN_VALUE;
                dp[i][j] = -10000000;
            }
        }
        dp[1][1] = a[1][1];
        for ( int i=2; i<=n; i++ ) {
            for ( int j=1; j<=i; j++ ) {
                dp[i][j] = Math.max( dp[i-1][j-1]+a[i][j], dp[i-1][j]+a[i][j] );
            }
        }
        int res = Integer.MIN_VALUE;
        for ( int i=1; i<=n; i++ ) {
            res = Math.max( res, dp[n][i] );
        }
        out.println(res);
        out.flush();
    }
    public static int in() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。
输入格式
第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N≤1000，
−109≤数列中的数≤109
输入样例：
7
3 1 2 1 8 5 6
输出样例：
4

package luogu.dp.线性DP;
import java.io.*;
public class 最长上升子序列 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws IOException {
        int n = in();
        int[] a = new int[n+1];
        for ( int i=1; i<=n; i++ ) {
            a[i] = in();//读入
        }
        int[] dp = new int[n+1];//存最长上升子序列的长度
        for ( int i=1; i<=n; i++ ) {
            dp[i] = 1;//最长上升子序列长度至少为1
            for ( int j=1; j<i; j++ ) {
              //如果第j个数小于i，进行比较取较大者
                if ( a[i]>a[j] ) dp[i] = Math.max( dp[i], dp[j]+1 );
            }
        }
        int res = -1;
        //找出最长的长度
        for ( int i=1; i<=n; i++ ) {
            res = Math.max( res, dp[i] );
        }
        out.println(res);
        out.flush();
    }
  //读入
    public static int in() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

package luogu.dp.线性DP;
import java.io.*;
public class 最长上升子序列 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws IOException {
        int n = in();
        int[] a = new int[n+1];
        for ( int i=1; i<=n; i++ ) {
            a[i] = in();
        }
        int[] dp = new int[n+1];//存最长上升子序列的长度
        int[] index = new int[n+1];//由那个位置转化而来
        for ( int i=1; i<=n; i++ ) {
            dp[i] = 1;//最长上升子序列长度至少为1
            for ( int j=1; j<i; j++ ) {
//                if ( a[i]>a[j] ) dp[i] = Math.max( dp[i], dp[j]+1 );
                if ( a[i]>a[j] ) { //如果a[j]小于a[i]，说明可以构成上升序列
                    if ( dp[i] < dp[j]+1 ) { //dp[i] < dp[j]+1 找到更长的上升子序列
                        dp[i] = dp[j]+1; //更新长度
                        index[i] = j; //更新由哪个数过来的
                    }
                }
            }
        }
        int res = -1;//子序列长度
        int idx = 1;//子序列结尾的数的下标
        for ( int i=1; i<=n; i++ ) { //遍历寻找
//            res = Math.max( res, dp[i] );
            if ( res < dp[i] ) {
                res = dp[i];
                idx = i;
            }
        }
        out.println(res);
        out.flush();
        //输出最长上升子序列
        while( idx>0 ) {
            out.print( a[idx]+" " );
            out.flush();
            idx = index[idx];
        }
    }
    public static int in() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
}

输入：
7
3 1 2 1 8 5 6
输出：
4
6 5 2 1 

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入格式
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出格式
输出一个整数，表示最大长度。
数据范围
1≤N,M≤1000
输入样例：
4 5
acbd
abedc
输出样例：
3

package luogu.dp.线性DP;
import java.io.*;
public class 最长公共子序列 {
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    public static void main(String[] args) throws IOException {
        int n = inInt();
        int m = inInt();
        char[] a = inStr().toCharArray();
        char[] b = inStr().toCharArray();
        int[][] dp = new int[n+1][m+1];//a b两个字符串，组合，二维数组
        for ( int i=1; i<=n; i++ ) {
            for ( int j=1; j<=m; j++ ) {
                // 数组a或数组b向后移动一个位置进行比较
                dp[i][j] = Math.max( dp[i-1][j], dp[i][j-1] );
                if ( a[i]==b[j] ) { //当a b两个数组相同时一起向后移动一个位置
                    dp[i][j] = Math.max( dp[i][j], dp[i-1][j-1]+1 );
                }
            }
        }
        out.println(dp[n][m]);
        out.flush();
    }
    public static int inInt() throws IOException {
        in.nextToken();
        return (int) in.nval;
    }
    public static String inStr() throws IOException {
        in.nextToken();
        return " " + in.sval;//下标从1开始存放字符
    }
}