数塔问题

本题采用记忆化搜索
如果暴力搜索的话，时间复杂度为$O(2^{n^2})$，由于题目规定$n\le100$，所以会超。
再想想正解：
我们可以发现暴搜会搜到很多很多重复的情况，浪费时间，所以我们可以在第一次搜到这个节点时把情况记录下来，如果下次再搜到这个节点时，直接返回之前统计好的情况，就不用再统计一遍，大大减小时间复杂度。
时间复杂度：$O(n^2)$

C++代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <list>
#include <map>
#define P(x) x>0?x:0
#define INF 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef vector<int>:: iterator VITer;
const int maxN=105;

int f[maxN][maxN];
int a[maxN][maxN];
int N;

int solve(int i,int j) {
    if(f[i][j]>=0)
        return f[i][j];
    else
        return f[i][j]=a[i][j]+(i==N? 0 : max(solve(i+1,j),solve(i+1,j+1) ) );
        // 如果i=n，说明搜索结束，f[i][j]设为0；否则就往下搜
}

int main() {
    scanf("%d",&N);
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=i; j++) {
            scanf("%d",&a[i][j]);
        }
    }
    memset(f,-1, sizeof(f));
    printf("%d\n",solve(1,1));
    return 0;
}