[每日算法]数字三角形

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

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

在上面的样例中,从 7→3 → 8 → 7 → 5 的路径产生了数字和最大。

输入格式

第一个行一个正整数 r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

输入输出样例

样例#1	输出#1
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30

说明/提示

【数据范围】
对于 100% 的数据，1≤r≤1000，所有输入在 [0,100] 范围内。

题目翻译来自NOCOW。

USACO Training Section 1.5

IOI1994 Day1T1

题解

很明显这是个动态规划问题，如果用贪心求解那么只能得到局部最优解而不能得到全局最优解。 这个题目从上向下求解会比较麻烦，但是如果逆向求解即从下向上求解就很比较简单，状态转移方程为 f 【x】【y】=max(f【x+1】【y】,f【x+1】【y+1】)+a【x】【y】（f【i】【j】表示走到第i层第j个时的最大值）。最后输出a数组的最大值即可。

源代码

#include <iostream>
#include <cmath>
using namespace std;

int numberTriangles(int** nums, int n)
{
    int i, j;
    //从倒数第二排开始处理
    for (i = n - 2;i >= 0;i--)
    {
        for (j = 0;j <= i;j++)
        {
            nums[i][j] += max(nums[i + 1][j], nums[i + 1][j + 1]);
        }
    }
    return nums[0][0];
}

int main()
{
    int n, i, j, num;
    cin >> n;

    //动态开辟空间
    int** nums = new int* [n]; //开辟行
    for (i = 0; i < n; i++)
        nums[i] = new int[n]; //开辟列

    //将数据载入内存
    for (i = 0;i < n;i++)
    {
        for (j = 0;j <= i;j++)
        {
            cin >> num;
            nums[i][j] = num;
        }
    }

    //动态规划处理后输出结果
    cout << numberTriangles(nums, n);

    //释放开辟的资源
    for (i = 0; i < n; i++)
        delete[] nums[i];
    delete[] nums;

    return 0;
}