金币

题目描述

小招在玩一款游戏：在一个N层高的金字塔上，以金字塔顶为第一层，第i层有i个落点，每个落点有若干枚金币，在落点可以跳向左斜向下或向右斜向下的落点。若知道金字塔的层数N及每层的金币数量分布，请计算小招在本次游戏中可以获得的最多金币数量。

输入描述:

输入共有N + 1行(N ≤ 1024)，第一行为高度N，第二行至N + 1行 ，为该金字塔的金币数量分布。

输出描述:

输出金币数量。

示例1

输入
5
8
3 8
8 1 0
4 7 5 4
3 5 2 6 5

输出
31

思路

将最后一行元素，初始化为dp数组，依次向上计算，输出所得结果，而且避免了边界条件的判断

import java.util.LinkedList;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int len = in.nextInt();
        LinkedList<LinkedList<Integer>> list = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            LinkedList<Integer> input = new LinkedList<>();
            for (int j = 0; j <=i; j++) {
                input.add(in.nextInt());
            }
            list.add(input);
        }

        int[] dp = new int[len];
        for (int i = 0; i < len; i++) {
            dp[i] = list.get(len-1).get(i);
        }
        for (int i = len-2; i >=0 ; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.max(dp[j],dp[j+1])+list.get(i).get(j);
            }
        }
        System.out.println(dp[0]);

    }
}