数字三角形（暴力备忘录和动态规划）

---

前言

提示：这里可以添加本文要记录的大概内容：
例如：今天我们学习一下数字三角形的最优路径，用到了暴力（递归），备忘录法，和动态规划。其实备忘录法也是动态规划的一种，又叫查表法。主要的差别看下文。

---

一、#什么是数字三角形及要解决的问题

示例：

1. 数字三角形其实是一堆无序的数字组成一个三角形

2. 要解决的问题
   我们要解决的问题就是怎么样选择一个最优路径，（从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。编写一个程序求出最佳路径上的数字之和。）路径上的每一步只能从一个数走到下一层上和它最近的左边的数或者右边的数。
   上图的最优路径就是
   
   7+3+8+7+5=30，这条路径是最大路径。

二、数组存入

我们可以用二维数组存这些数据。
7
3 8
8 1 2
2 7 4 4
4 5 2 6 5
本来的左边的数或者右边的数就变成了直接下面和右下的数据

//n是该二维数组的层数
int a[][]=new int[n][n];

1
2
3

三、方法及代码

1.暴力（递归）

暴力意味着穷举，意思是将每一个路径都找出来。但暴力也需要有技巧的暴力。在这里我们就用到了递归。
我们先把这个数组划分为一个个简单的数组，如


根据规定，只能走下一层最近的两个数字，也就是说每个数字只存在两种情况，（7的选择：3or8；3的选择：8or1）

那我们可以用递归的方法来决定最优路径（自顶向下分解问题，自底向上求解）穷举路径。
我们直接看最下面一行和倒数第二层数据。2的最优路径是5，7的最优路径是6，4的最优路径是6，4的最优路径是6。
我们直接看倒数第二层数据和倒数第三层数据。8的最优路径是2+5，1的最优路径是7+6，2的最优路径是4+6。
其实，一个数的最优路径就是这个本身的值再加上直接下面和右下数据的最优路径（递归思想）
而递归的结束条件就是递归到了最上面一层。
代码如下（示例）：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
   
 public static void main(String[] args) {
   
  Scanner in=new Scanner(System.in);
  while(in.hasNext()) {
   
  //数据层数
      int n=in.nextInt();
      int a[][]=new int[n][n];
      for(int i=0;i<n;i++){
   
       for(int j=0;j<=i;j++){
   
        a[i][j]=in.nextInt();
       }
      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19