数字三角形


题目描述

img

图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;
}

文章作者: 瑾年
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 瑾年 !
  目录