动态规划初步

算法1

(DP) $O(n^2)$

$a[x]$ 为原数组
$f[x][y]$ 为动归数组

动归方程转移式

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

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int n;
int a[600][600], f[600][600], res;

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
        {
            cin >> a[i][j];
        }

    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
        {
            f[i][j] = -10e7;
        }

    f[1][1] = a[1][1];
    for (int i = 2; 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]);
        }


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

    cout << f[n][n];

}