题意：有n行数，以金字塔的形式排列，第一行一个数字，第二行两个数字，依次类推...，找一条从第一行到第n行的路线，使得路线的权值最大，输出权值
解题思路：dp.简单的动态规划，状态转移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]，dp[i][j]表示以第i行第j列的元素作为终点的路线中的最大权值
代码：
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <cstdio> using namespace std; int n; int a[360][360],dp[360][360]; int main() { cin>>n; memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { cin>>a[i][j]; } } for(int i=0;i<n;i++) { for(int j=0;j<=i;j++) { dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+a[i][j]; } } int ans=0; for(int i=0;i<n;i++) { ans=max(ans,dp[n-1][i]); } cout<<ans<<endl; return 0; }
