题解 1177: 三角形 C++

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
const int N = 110;
int q[N][N],f[N][N];
int main()
{
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                scanf("%d",&q[i][j]);
            }
        }
        int num=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                f[i][j]=f[i-1][j]+q[i][j];
                if(j<=n)//防止越界
                f[i][j]=max(f[i][j],f[i-1][j-1]+q[i][j]);
                num=max(num,f[i][j]);
            }
        }

        cout<<num<<endl;
    }
    return 0;
}