动态规划 三角形

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

const int N=110;

int f[N][N],a[N][N];

int n,m;

int main()

{

    cin>>m;

    while(m--)

    {

        cin>>n;

        for(int i=1;i<=n;i++)

            for(int j=1;j<=i;j++)

                cin>>a[i][j];

        for(int i=1;i<=n;i++)

            for(int j=1;j<=i+1;j++)   f[i][j]=-1e9;

        f[1][1]=a[1][1];

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=i;j++)    //状态转移方程

                f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);

        }

        int res=-1e9;

        for(int i=1;i<=n;i++)   res=max(res,f[n][i]);

        cout<<res<<endl;

    }

    return 0;

}