数塔问题--动态规划

【问题描述】

给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。

【输入形式】

输入时第一行一个整数n，表示该数塔的行数，其余n行表示该塔每行的数值

【输出形式】

输出包含两行，第一行为最大路径上的数值之和， 第二行n个数字为从上而下最大路径数值

【样例输入】
5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16

【样例输出】
59
9 12 10 18 10

（一）将数塔储存在一个二维数组里
（二）从倒数第二层开始，逐渐向上找到每一层每个位置加上下层可加 位置后的最大值
（三）利用中间数组存储动态规划过程中结果
（四）循环（二）直到第一层，即最后的中间数组存储的最大值即为路径数值和的最大值
（五）寻找最大值路径：通过存储的中间数组的值从上往下一次判断是否是组成最大值的路径，如果是则为该层所取值

//数塔

#include<bits/stdc++.h>
#pragma warning(disable:4996)

using namespace std;
int get_max(int x, int y);

int main(int argc, char** argv)
{
int M;cin>>M;
int i = 0, j = 0, k = 0;
int map[M][M];
int result[M][M];
// freopen(“input.txt”, “r”, stdin);
memset(result, 0, sizeof(int)MM);
memset(map, 0, sizeof(int)MM);

for (i = 0; i < M; i++)//读入塔
{
    for (j = 0; j < i + 1; j++)
    {
        cin >> map[i][j];
        if (i == M - 1)
        {
            result[i][j] = map[i][j];
        }
    }
}

for (k = M - 2; k >= 0; k--)//上塔 第k层,
{
    for (i = 0; i < k + 1; i++)//统计 一行的每一个节点, 当前点是(k,i)
    {
        result[k][i] = get_max(map[k][i] + result[k + 1][i], map[k][i] + result[k + 1][i+1]);
    }
}

cout << result[0][0] <<endl;
int target = result[0][0] - map[0][0];
cout << map[0][0] <<' '; //从塔顶至塔底 输出路径
i = 1;
while ( i<M)
{
    for (j = 0; j < i+1; j++)
    {
        if (result[i][j] == target)
        {
            target = result[i][j] - map[i][j];
            cout << map[i][j] <<' ';
            break;
        }
    }
    i++;
}
cout << endl;

return 0;

}

int get_max(int x, int y)
{
return (x > y) ? x : y;
}