数字三角形 Number Triangles

我的第200道题目.

可以当成动态规划的模板了,非常简单.主要是想先把动态规划的内容回忆起来,先前觉得难跳过了这一部分的刷题.

通过这种方式存储数据后,即可用s[i][j]来表示第i行第j个数,且d[i + 1][j], d[i + 1][j + 1]分别表示该数字左下方和右下方的数字.

要退出最大路径,从最后一行往上推,用dp[i][j]存储从位置(i,j)到最后一行能产生的最大路径.那么:

dp[n][j] = s[n][j].

dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + s[i][j].(注意第i + 1行是第i行的下一行)

实现如下:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n;
int s[1010][1010], dp[1010][1010];

int rec(){
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + s[i][j];

    return dp[1][1];
}

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

    printf("%d\n", rec());

    return 0;
}

View Code

注意到不需要先初始化dp[n][j],在第一次循环时已经使得dp[n][j] = dp[n + 1][j] + s[n][j],dp[n + 1][j]初始值为0,效果即dp[n][j] = s[n][j].

最后输出最高点到最后一行能产生的最大路径dp[1][1]即答案.