简单线性DP

数字三角形--简单线性DP

题目链接：数字三角形

解题代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int N=510;
    static int INF= (int) -1e9;
    static String[] q;
    static int[][]f=new int[N][N];
    static int[][]a=new int[N][N];
    public static void main(String[] args)throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        q=br.readLine().split(" "); 
        int n= Integer.parseInt(q[0]);
        for(int i=1;i<=n;i++){
            q=br.readLine().split(" ");
            for(int j=1;j<=i;j++){
                a[i][j]= Integer.parseInt(q[j-1]);
            }
        }
        for(int i=0;i<=n;i++)
            for(int j=0;j<=i+1;j++)
                f[i][j]=INF;
        f[1][1]=a[1][1];

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

        int x=0;
        for(int i=1;i<=n;i++)
            if(f[n][i]>x)x=f[n][i];
        System.out.println(x);
    }
}

最长上升子序列

题目链接：最长上升子序列

题解代码：

//package 线性DP.最长上升子序列;

import java.util.Scanner;

public class Main {
    static int N=1010;
    static int[]f=new int[N];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[n+1];
        
        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[i]>a[j])
                    f[i]=Math.max(f[i],f[j]+1);
            }
        }
        int x=f[1];
        for(int i=2;i<=n;i++)
            if(f[i]>x)x=f[i];
        System.out.println(x);
    }
}