蓝桥与力扣刷题（蓝桥 数字三角形）

题目：

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和（路径上的每一步只可沿左斜线向下或右斜线向下走）。

输入描述

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

下面的 𝑁 行给出数字三角形。数字三角形上的数都是 0 至 99 之间的整数。

输出描述

输出一个整数，表示答案。

输入输出样例

示例

输入

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

输出

30

解题思路+代码：

代码：

import java.util.Scanner;
// 1: 无需 package
// 2: 类名必须 Main, 不可修改public class Main {static int[][] triangle; // 存储三角形数据static int[][] memo; // 记忆化存储static int n ; // 三角形的行数public static void main(String[] args) {Scanner scan = new Scanner(System.in);n = scan.nextInt(); //获取三角形的行数triangle  = new int[n][n];memo = new int[n][n]; // 初始化缓存数组// 初始化 memo 数组for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {memo[i][j] = -1; // -1 表示未计算}}// 读取三角形数据for(int i = 0; i<n; i++){for(int j = 0; j<=i; j++){triangle[i][j] = scan.nextInt();}}scan.close();int sum = 0;// 计算最大路径和（暴力搜索）System.out.println(bruteForce(0,0));}/*** 递归暴力搜索，计算从 (i, j) 到底部的最大路径和*/public static int bruteForce(int i,int j){// 递归出口：到底部时返回当前值if(i == n-1){return triangle[i][j];}// 如果已经计算过，直接返回if (memo[i][j] != -1) {return memo[i][j];}// 递归计算左右路径的最大值int left = bruteForce(i+1,j);int right = bruteForce(i+1,j+1);// 取最大值，并存入 memo 以备下次使用memo[i][j] = Math.max(left, right) + triangle[i][j];return memo[i][j];}
}

总结：这道题难度很大，可以用 动态规划（DP） 解决，也可以用 深度优先搜索（DFS）+ 记忆化搜索，或者 广度优先搜索（BFS） 解决，但 BFS 并不高效，因为BFS会遍历所有可能路径。我这里的解法是使用记忆化搜索（递归 + 缓存），因为尝试了暴力递归去解会运行超时，所以必须加上缓存，使用 memo[][] 记忆化数组，避免重复计算，将时间复杂度降为O(N^2)。