题目描述

图1显示了一个数字三角形。编写一个程序,计算从顶部开始到底部某处的路径上传递的最大数字总和。
每个步骤可以沿对角线向下滑动,也可以沿斜向下滑动到右侧。

输入

您的程序是从标准输入读取。
第一行包含一个整数N:三角形中的行数。
以下N行描述了三角形的数据。
三角形中的行数大于 1但小于等于 100.
三角形中的数字全部为整数,介于0到99之间。

输出

你的程序是写入标准输出。
最高总和写为整数。

输入样例

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

输出样例

30

分析

分析1

通过分析输入样式,我们观察到,一个数去加的下一行对应的列以及下一行j+1列。
故这道题可以用递归求解?

  • 递归参数:一个数的横纵坐标
  • 约束条件:当函数行数等于最大行数N
    代码如下
    #include <bits/stdc++.h>
    using namespace std;
    //递归程序
    const int M = 1000;
    int d[M+10][M+10];
    int n = 0 ;
    int maxs(int i , int j)
    {
    if(i == n)
    {
    return d[i][j];
    }
    else
    {
    int a = maxs(i+1,j);
    int b = maxs(i+i,j+1);
    if(a > b){ return a + d[i][j];}
    else { return b + d[i][j];}
    }
    }
    int main() {
    int n = 0 ;
    cin >> n ;
    for(int i = 0 ; i < n ; ++i)
    for(int j = 0 ; j < i ; ++j)
    {
    cin >> d[i][j];
    }
    cout<<maxs(1,1);
    return 0;
    }

答案是否定的,因为你会发现从第三行开始,中间的因为递归,全部被重复计算多次,如果当数字三角型足够大时,题目肯定超时。

分析2

分析1的递归显然是不能用了。但我们设一个二维数组,将算过的值保存起来,避免二次或多次计算。
以下是记忆型动规的代码

const int M = 1000;
int d[M+10][M+10];
int n = 0 ;
int Max_Array[M+10][M+10];
int maxs(int i , int j)
{
if(i == n )
{
return d[i][j];
}
else
{
if(Max_Array[i+1][j] == -1 ){Max_Array[i+1][j] = maxs(i+1,j);}
if(Max_Array[i+1][j+1] == -1){Max_Array[i+1][j+1] = maxs(i+1,j+1);}
if(Max_Array[i+1][j] > Max_Array[i+1][j+1]) { return Max_Array[i+1][j] + d[i][j];}
else{ return Max_Array[i+1][j+1] + d[i][j];}
}
}
int main() {
int n = 0 ;
cin >> n ;
for(int i = 0 ; i < n ; ++i)
for(int j = 0 ; j < i ; ++j)
{
cin >> d[i][j];
Max_Array[i][j] = - 1;
}
cout << maxs(1,1);
return 0;
}

分析3

分析2有效地解决了超时的问题,但开出了过多的空间。
通过观察我们不难发现,第r行可以由r+1行算出。
比如说,第四行的第一个数的最大路径值,等于第五行它的同列与第五行同列+1列的最大值加这个第四行的数的值。
而且当第四行第一个数被算出后,第五行第一个数就没用了。这时我们可以让第四行第一行值覆盖第五行第一个值。

这就是滚动数组,对二维数组进行降维。
这种动规方法为递推式动规,即用已知的值计算出未知的值。
参考代码如下

const int M = 1000;
int d[M+10][M+10];
int n = 0 ;
int Maxs[M+10];
int main() {
int n = 0 ;
cin >> n ;
//input
for(int i = 0 ; i < n ; ++i)
for(int j = 0 ; j < i ; ++j)
{
cin >> d[i][j];
}
//init status
for(int i = 0 ; i < n ; ++i){Maxs[i] = d[n][i];}
//start
for(int i = n-2 ; i <=0 ; ++i)
{
for(int j = 0 ; j < i ; ++j)
{
Maxs[i] = max(d[i][j] + Maxs[i] , d[i][j]+ Maxs[i+1]);
}
}
cout << Maxs[0];
return 0;
}

谢谢访问