//记忆化搜索 #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; }
解题思路:
注意事项:
参考代码:
0.0分
6 人评分