信息学奥赛一本通（1258：【例9.2】数字金字塔）

1258：【例9.2】数字金字塔

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 20019     通过数: 11518

【题目描述】

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

在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。

【输入】

第一个行包含R(1≤R≤1000)，表示行的数目。

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

所有的被供应的整数是非负的且不大于100。

【输出】

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

【输入样例】

5
13
11 8
12 7  26
6  14 15 8
12 7  13 24 11

【输出样例】

86

【分析】

方法1：顺推

设a[i][j]存储数塔，f[i][j]则记录从起点到第 i 层第 j 列的路径数字和。

（1）划分阶段。

        阶段：每一层就是一个阶段；样例中共有五个阶段。

（2）确定状态和状态变量。

        状态：二维数组中的每个值就是状态。状态信息用f[i][j]表示。

（2）确定决策并写出状态转移方程。

        f[i][j]的值从哪来？当然是从上面第 i-1 行的第 j 列和第 j-1 列来。决策：来自上？ 或是 来自左上？，策略：最大化路径。故：

        状态转移方程： 

（4）寻找边界条件。

        顺推时， 边界：f[1][1]=a[1][1]。目标：max(f[n][j])

（5）设计并实现程序。

【参考代码1】

#include <stdio.h>
#define MAXN 1010
 
int a[MAXN][MAXN];       //存储数塔数据 
int f[MAXN][MAXN];       //f[i][j]表示从起点到i层j列的路径数字和 

int max(int x,int y)
{
    return x > y ? x : y;
}
int main()
{
    int i,j,n,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
    
    f[1][1]=a[1][1];
     
    for(i=2;i<=n;i++)
        for(j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];  //状态转移方程 

	ans=0;
	for(i=1;i<=n;i++)          //max(f[n][j]) 
		ans=max(ans,f[n][i]);
    printf("%d",ans);
    return 0;
}

方法2：逆推法

逆推时，f[i][j]的值从哪来？是从下面第 i+1 行的第 j 列和第 j+1 列来。状态转移方程为：

 边界：f[n][j]=a[n][j]。目标：f[1][1]。 

  【参考代码2】

#include <stdio.h>
#define MAXN 1010
 
int a[MAXN][MAXN];        //存储数塔数据 
int f[MAXN][MAXN];        //f[i][j]表示从起点到i层j列的路径数字和 

int max(int x,int y)
{
    return x > y ? x : y;
}
int main()
{
    int i,j,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=i;j++)
            scanf("%d",&a[i][j]);
     
    for(i=1;i<=n;i++)
        f[n][i]=a[n][i];
     
    for(i=n-1;i>=1;i--)
        for(j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];   //状态转移方程 
    
    printf("%d",f[1][1]);   //目标 f[1][1] 
    return 0;
}

http://ybt.ssoier.cn:8088/problem_show.php?pid=1258