数字三角形

柔光的暖阳◎ 2024-03-25 14:02 78阅读 0赞

![707e1f04e331a2967263ea5a5377aada.png][]

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

#### **输入描述** ####

输入的第一行包含一个整数 � (1≤�≤100)*N* (1≤*N*≤100)，表示三角形的行数。

下面的 �*N* 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

解题思路：

*  采用动态规划，计算出顶点到底部每个点所走的距离

*  如果行数为奇数，则结果为中间的值

*  若为偶数，则为中间两个值的最大值

动态方程

if (i>0){//i为行数
                        if (i1==0){//第一列
                            dp[i][i1]+=dp[i-1][i1];
                        }else if (i==i1){//对角线列
                            dp[i][i1]+=dp[i-1][i1-1];
                        }else {
                            dp[i][i1]+=Math.max(dp[i-1][i1],dp[i-1][i1-1]);
                        }

代码为：

import java.util.Scanner;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int [][]dp=new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int i1 = 0; i1 < i + 1; i1++) {
                    dp[i][i1]=sc.nextInt();
                }
            }
            sc.close();
            for (int i = 0; i < dp.length; i++) {
                for (int i1 = 0; i1 < i + 1; i1++) {
                    if (i>0){
                        if (i1==0){
                            dp[i][i1]+=dp[i-1][i1];
                        }else if (i==i1){
                            dp[i][i1]+=dp[i-1][i1-1];
                        }else {
                            dp[i][i1]+=Math.max(dp[i-1][i1],dp[i-1][i1-1]);
                        }
                    }
                }
            }
    
            if(n%2==1){
                System.out.println(dp[n-1][(n-1)/2]);
            }
            if (n%2==0){
                int res=Math.max(dp[n-1][(n-1)/2],dp[n-1][(n-1)/2+1]);
                System.out.println(res);
            }
            
        }
    }

测试结果：

![compatible][]

[707e1f04e331a2967263ea5a5377aada.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/95a89b23cc894123a57e987ac8e9e3ae.png
[compatible]: https://ksc-bj.ag.wps.cn/api/object/2_e7b2a1bfedda46dcb3d31540767e54b7/compatible