AcWing AC898

每日一题D2

URL:https://www.acwing.com/problem/content/106/

视频URL:https://www.bilibili.com/video/BV1LT4y1N7YD

博客URL:https://www.cnblogs.com/sweepy/p/ac898.html

题面描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

输入格式

第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

AC Code

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int w[N][N], f[N][N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= i; j++)
        {
            cin >> w[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        f[n][i] = w[n][i];
    }
    for (int i = n - 1; i; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            f[i][j] += max(f[i + 1][j] + w[i][j], f[i + 1][j + 1] + w[i][j]);
        }
    }
    cout << f[1][1] << endl;
    return 0;
}

思路

1. $O(2^{n-1})$的写法
2. 暴力搜索$2^{499}$
3. 动态规划
4. $$f[i][j] += \max\left( f[i + 1][j] + w[i][j], f[i + 1][j + 1] + w[i][j]\right)$$