试题 历届试题 数字三角形
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
p1.png
上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。
输入格式
输入的第一行包含一个整数 ，表示三角形的行数。下面的 行给出数字三角形。数字三角形上的数都是 至 之间的整数。
输出格式
输出一个整数，表示答案。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Data
样例输出
27
题目分析:经典的动态规划问题,首先要仔细读题,此题好像是ACM真题改变的老题,题目中的加粗重点阅读,原题没有这句话会简单很多,直接最简单的递归,但是容易超时,这里不用.我们采用倒推方法,从最后一行倒推到第一行.
ps:本题是改编的蓝桥杯真题,原题测试结果是30,没有我在题中加粗的哪句话
这里首先写几个测试用例,找下规律
测试用例1
7
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
3 2 5 7 9 1
5 1 4 6 8 3 4
测试用例2
10
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
3 2 5 7 9 1
5 1 4 6 8 3 4
4 3 8 4 1 3 2 3
4 3 8 4 1 3 2 3 1
4 3 8 4 1 3 2 3 2 1
可以发现题中我加粗的要求,符合只有从第n-1行的(n-1)/2和n/2列开始才可以满足向左下走的次数与向右下走的次数相差不能超过1,比如测试用例1从(7-1)/2=3和7/2=3开始(倒数第一行的6),测试用例2从(10-1)/2=4和10/2=5开始(倒数第一行的1和3).
测试用例1往上推6只能向左上和右上走5和7走
测试用例2往上推1和3只能走4,1,3
然后我们把不需要的全部置为0,测试用例2最后一行(n-1)为
0 0 0 0 1 3 0 0 0 0
依次类推
10
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
3 2 5 7 9 1
1 4 6 8 3 0
0 0 8 4 1 3 0 0
0 0 0 4 1 3 0 0 0
0 0 0 0 1 3 0 0 0 0
最后用动态规划的思想每一步找出符合条件的值.
代码实现
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[][] = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { arr[i][j] = sc.nextInt(); } } int k=(n-1)/2; int k1=n/2+1; for(int i=n-1;k>0;--i,--k){ for(int j=0;j<k;++j) arr[i][j]=0; for(int j=k1;j<=i;++j) arr[i][j]=0; } for (int i = n - 2;i>=0; i--) { for (int j=0; j <=i; j++ ) { arr[i][j]+=Math.max(arr[i+1][j],arr[i+1][j+1]); } } System.out.println(arr[0][0]); }}