【Java每日一题,动态规划】数字金字塔

简介: 【Java每日一题,动态规划】数字金字塔

Introduction

给定一个如下图所示的数字三角形,从顶部出发,在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点,一直走到底层,要求找出一条路径,使路径上的数字的和最大。


7


3 8


8 1 0


2 7 4 4


Input

第一行包含整数 n,表示数字三角形的层数。

接下来 n 行,每行包含若干整数,其中第 i行表示数字三角形第i 层包含的整数。


所有输入整数绝对值小于20


Output

输出一个整数,表示最大的路径数字和。


Sample

input

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

output

30

Solution

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int[][] arr=new int[n][n];
        int num=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<num;j++){
                arr[i][j]=s.nextInt();
            }
            num++;
        }
        for(int i=n-1;i>=0;i--){
            if(i==n-1)continue;
            for(int j=0;j<=i;j++){
                arr[i][j]=Math.max(arr[i+1][j],arr[i+1][j+1])+arr[i][j];
            }
        }
        System.out.println(arr[0][0]);
    }
}

Experience

很久没用dp,第一时间竟然忘记怎么写了,哎。

相关文章
|
7月前
|
Java
0-1背包问题(Java详解)(动态规划)至少与恰好
0-1背包问题(Java详解)(动态规划)至少与恰好
59 1
【Java每日一题,动态规划,零钱兑换模板题】硬币组合数量
【Java每日一题,动态规划,零钱兑换模板题】硬币组合数量
|
6月前
|
Java
java输出倒立金字塔
java输出倒立金字塔
|
6月前
|
Java Python
分别使用python和java编写金字塔图形
分别使用python和java编写金字塔图形
|
6月前
|
算法 Java 决策智能
Java数据结构与算法:动态规划之背包问题
Java数据结构与算法:动态规划之背包问题
|
7月前
|
Java
用Java写数字金字塔
用Java写数字金字塔
82 7
|
7月前
|
算法 Java
给定一个字符串数组,如何找到其中最长的回文子串? 要求:编写一个Java函数,输入一个字符串数组,输出其中最长的回文子串。要求时间复杂度为O(n^2)。可以考虑使用动态规划或中心扩展的方法来优化算法。
给定一个字符串数组,如何找到其中最长的回文子串? 要求:编写一个Java函数,输入一个字符串数组,输出其中最长的回文子串。要求时间复杂度为O(n^2)。可以考虑使用动态规划或中心扩展的方法来优化算法。
88 1
【Java每日一题,动态规划,Map实现】最长定差子序列
【Java每日一题,动态规划,Map实现】最长定差子序列
【Java每日一题,动态规划】最长定差子序列
【Java每日一题,动态规划】最长定差子序列
力扣322. 零钱兑换 Java动态规划
给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。 你可以认为每种硬币的数量是无限的。
202 0
力扣322. 零钱兑换 Java动态规划