1.6.1 数字三角形

题目考查

递推

我们考虑当选择路径的时候, 如果我们从上往下看, 最终的路径数会有 n n n种, 分别以 a [ n ] [ 1 ] a[n][1] a[n][1]~ a [ n ] [ n ] a[n][n] a[n][n]作为路径的终点.

但是如果我们从下往上去看, 最终路径只会有 1 1 1种, 即 a [ 1 ] [ 1 ] a[1][1] a[1][1].

那么如果我们以这种思路去思考, 对于 a [ i ] [ j ] a[i][j] a[i][j], 相当于我可以从 a [ i + 1 ] [ j ] a[i + 1][j] a[i+1][j]和 a [ i + 1 ] [ j + 1 ] a[i + 1][j + 1] a[i+1][j+1]两个数中选择一个数字, 加到 a [ i ] [ j ] a[i][j] a[i][j]中. 很显然, 最终 a [ i ] [ j ] + = m a x ( a [ i + 1 ] [ j ] , a [ i + 1 ] [ j + 1 ] ) a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]) a[i][j]+=max(a[i+1][j],a[i+1][j+1]).

题目细节

1. 如果本题作为多组输入, 一定要注意初始化.

AC代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
const int N = 5E2 + 10;
int a[N][N];
int main()
{
    int n; cin >> n;
    rep(i, n) rep(j, i) scanf("%d", &a[i][j]);

    for (int i = n - 1; i >= 1; --i) {
    	for (int j = 1; j <= n; ++j) {
    		a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
    	}
    }
    cout << a[1][1] << endl;
    
    return 0;
}

END