蓝桥杯c语言杨辉三角形,杯底三角形100数字

算法训练数字三角形时间限制：1.0s 内存限制：256.0MB 问题描述　　（图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路　　径，使该路径所经过的数字的总和最大。　　●每一步可沿左斜线向下或右斜线向下走；　　●1＜三角形行数≤100；　　●三角形中的数字为整数0，1，…99；　　. 　　（图３.１－１）输入格式　　文件中首先读到的是三角形的行数。　　接下来描述整个三角形输出格式　　最大总和（整数）样例输入 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 样例输出 30

解题思路：这里其实主要是运用了动态规划，刚刚开始做这些题目的时候，自己对动态规划的思想也是理解的不好，但是做的多了之后，发现了一些规律。很多书上都会提到需要提出一个动态规划方程，那样就更好写程序了，我觉得吧，自己按照自己的理解的方式来也是可以的，不必那么死板。。
这个题目刚刚看到自己想到用树来解决，深度优先算法来解决，但是想想觉得太麻烦，然后看到题目要求，就是要求最大值，想到要不是左边的那个，要不是右边那个值，这样想想好像就有规律了，比如，我们倒过来想，从n个开始，现在比如输入n=5；那么a[4][4]的最大值是不是等于本身加上a[5][4] 和 a[5][5]的最大值(当然这样数组下标是从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]); }} 关于动态规划的内容可以看一下我的这篇博客

一看就懂的动态规划入门教程

算法-动态规划（1）