题目描述

blablabla

样例

blablabla

算法1

从下往上

Java 代码

import java.util.*;
import java.io.*;

public class Main{
    private static int N;
    private static int V;
    private static int[][] dp;
    private static int[][] a;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]); // 行数
        dp = new int[N+2][N+2];  
        a = new int[N+1][N+1];

        for (int i=1 ; i <= N ; i++){ 
            String[] nums = read.readLine().split("\\s+");
            for (int j = 1; j <= nums.length; j++) { 
                a[i][j] = Integer.parseInt(nums[j-1]);
            }
        }

        for(int i = N; i >= 1;i--){
            for(int j = 1; j <= i; j++){
                dp[i][j] = Math.max(dp[i+1][j+1], dp[i+1][j]) + a[i][j];
            }
        }

        System.out.println(dp[1][1]);

    }
}

算法2

优化

一维优化
关于滚动数组有个处理技巧，如果上一层是j,j+1, 那么j直接顺序枚举即可。如果上一层是j,j-1,那么需要保证j是在j-1之前更新，于是就需要倒序枚举。

Java 代码

import java.util.*;
import java.io.*;

public class Main{
    private static int N;
    private static int V;
    private static int[] dp;
    private static int[][] a;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]); // 行数
        dp = new int[N+2];  
        a = new int[N+1][N+1];

        for (int i=1 ; i <= N ; i++){ 
            String[] nums = read.readLine().split("\\s+");
            for (int j = 1; j <= nums.length; j++) { 
                a[i][j] = Integer.parseInt(nums[j-1]);
            }
        }

        for(int i = N; i >= 1;i--){
            for(int j = 1; j <= i; j++){
                dp[j] = Math.max(dp[j+1], dp[j]) + a[i][j];
            }
        }

        System.out.println(dp[1]);

    }
}