算法訓(xùn)練 數(shù)字三角形 時間限制：1.0s 內(nèi)存限制：256.0MB問題描述（圖３.１－１）示出了一個數(shù)字三角形。 請編一個程序計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最大。●每一步可沿左斜線向下或右斜線向下走；●1＜三角形行數(shù)≤100；●三角形中的數(shù)字為整數(shù)0，1，…99；.（圖３.１－１）輸入格式文件中首先讀到的是三角形的行數(shù)。接下來描述整個三角形輸出格式最大總和（整數(shù)）樣例輸入573 88 1 02 7 4 44 5 2 6 5樣例輸出30

解題思路：這里其實(shí)主要是運(yùn)用了動態(tài)規(guī)劃，剛剛開始做這些題目的時候，自己對動態(tài)規(guī)劃的思想也是理解的不好，但是做的多了之后，發(fā)現(xiàn)了一些規(guī)律。很多書上都會提到需要提出一個動態(tài)規(guī)劃方程，那樣就更好寫程序了，我覺得吧，自己按照自己的理解的方式來也是可以的，不必那么死板。。
這個題目剛剛看到自己想到用樹來解決，深度優(yōu)先算法來解決，但是想想覺得太麻煩，然后看到題目要求，就是要求最大值，想到要不是左邊的那個，要不是右邊那個值，這樣想想好像就有規(guī)律了，比如，我們倒過來想，從n個開始，現(xiàn)在比如輸入n=5；那么a[4][4]的最大值是不是等于本身加上a[5][4] 和 a[5][5]的最大值(當(dāng)然這樣數(shù)組下標(biāo)是從1開始)，接下來，a[3][4] += a[4][4] 和a[4][5]。這樣好像就可以解決了。方程好像不就是a[i-1][j]+= Math.max(a[i][j], a[i][j+1])，這樣就解決了。

package com.sihai.advance;import java.util.Scanner;public class sanjiaoxing{ public static void main(String[]args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[][]a = new int[n+1][((1+n)*n)/2+1];for(int i=1 ; i<=n ; i++){for(int j=1 ; j<=i ; j++){a[i][j] = sc.nextInt();}}for(int i=n ; i>=1 ; i--){for(int j=1 ; j<=i-1 ; j++){a[i-1][j]+= Math.max(a[i][j], a[i][j+1]);}}System.out.println(a[1][1]);} }

關(guān)于動態(tài)規(guī)劃的內(nèi)容可以看一下我的這篇博客

一看就懂的動態(tài)規(guī)劃入門教程

算法-動態(tài)規(guī)劃（1）

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯-数字三角形 （java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。