数字三角形

题目描述：从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入
输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。
下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出
输出最大的和。

样例输入

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

样例输出

30

思路模拟：算一条路径最大的和，应从第一行算到三角形底行。
核心代码： max(maxsum[i+1][j], maxsum[i+1][j+1]) + d[i][j];

方法一：记忆化递归

用Maxnsum当做记忆化数组，初始化为-1，不等于-1时，表示之前已计算过当前位置的最大值，可以直接调用。避免递归的重复计算。
从第一行开始计算到最后一行。
递归边界：递归至最后一行（i 等于N）

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn = 101;
int p[maxn][maxn];
int Maxnsum[maxn][maxn];
int N;
int maxnsum(int i, int j) {
  if (Maxnsum[i][j] != -1) {
    return Maxnsum[i][j];
  }
  if (i == N) {
    Maxnsum[i][j] = p[i][j];
  } else {
    int x = maxnsum(i+1,j);
    int y = maxnsum(i+1,j+1);
    Maxnsum[i][j] = max(x,y)+p[i][j];
  }
  return Maxnsum[i][j];
}
int main() {
  fio
  cin >> N;
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= i; j++) {
      cin >> p[i][j];
      Maxnsum[i][j] = -1;//为-1时代表还未计算到 
    }
  }
  cout << maxnsum(1,1) << endl;
}

方法二：递推

比递归方法更高效。
递推方法从最后一行往上计算。
模拟：
①若计算最后一行最大和，则值为本身，故在二维数组第n行中填入三角形第n行的数值。

②再在n-1行从左至右依次计算最大和，例如：第n-1行的2应在第n行的4和5之间选一个最大值5，相加得7并填入2所在格子。
在这里插入图片描述
③同上填满格子，根据思路可知，从第一行计算的最大和应为三角形的最大和，故输出二维数组第一行第一个格子的值即可。
在这里插入图片描述

#include<bits/stdc++.h>
#define fio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn = 101;
int d[maxn][maxn];
int maxsum[maxn][maxn];

int main() {
  fio
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      cin >> d[i][j];
    }
  }
  //若从最后一行计算maxsum，则值等于自身 
  for (int j = 1; j <= n; j++) {
    maxsum[n][j] = d[n][j];
  }
  //从下往上计算 
  for (int i = n-1; i > 0; i--) {
    for (int j = 1; j <= i; j++) {
      maxsum[i][j] = 
      max(maxsum[i+1][j], maxsum[i+1][j+1]) + d[i][j];
    }
  }
  cout << maxsum[1][1]<<endl;
}