三角形 （C++代码）记忆化搜索

//记忆化搜索
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int    T , n , A[100][100],d[100][100],vis[100][100];
int dp(int i,int j){
    if(vis[i][j])  return d[i][j];
    vis[i][j]=1;
    d[i][j]=A[i][j];
    if(i<n)  d[i][j]+=max(dp(i+1,j),dp(i+1,j+1));
    return d[i][j];
  }
int main(void){
    cin >> T;
    while(T--){
        memset(vis,0,sizeof(vis));
        memset(d,0,sizeof(d));
        cin >> n;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
        cin >> A[i][j];
        cout << dp(1,1)<< endl;
    }
    return 0;
}

解题思路:





注意事项:





参考代码: