题目描述

附图 ：

blablabla

算法1

(数字三角形dp) $O(n^2)$

参考文献

算法提高课 lyd蓝书

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 110;
int g[N][N];
int f[N][N];
int n, m;

void dp()
{
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = max(max(f[i-1][j], f[i][j-1]) + g[i][j], f[i][j]);
        }

    cout << f[n][m] << endl;
}

void solve()
{
    memset(f, 0, sizeof f);
    memset(f, 0, sizeof g);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> g[i][j];

    dp();
}

int main()
{
    int T; cin >> T;
    while (T --) {
        solve();
    }
    return 0;    
}