动态规划—数字三角形问题

╰+哭是因爲堅強的太久メ 2022-07-11 01:52 167阅读 0赞

数字三角形问题  
Time Limit: 1000MS Memory Limit: 65536KB  
Problem Description  
给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。  
![这里写图片描述][SouthEast]  
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。  
Input  
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0..99之间。  
Output  
输出数据只有一个整数，表示计算出的最大值。  
Example Input

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

Example Output

Hint  
动态规划 /（全局数组 全局变量 函数 define）  
Author

#include <stdio.h>
    #define max(a, b) (a > b)? a: b//define的灵活应用
    
    int a[104][104], n;//定义全局数组和全局变量
    
    void sca()
    {
        int i, j, max1;
        for(i = 0; i < n; i++){
        
            for(j = 0; j <= i; j++){
        
                scanf("%d", &a[i][j]);
                if(j == 0 && i != 0)
                    a[i][j] += a[i-1][j];//动态规划思想
                else if(j == i && i != 0)
                    a[i][j] += a[i-1][j-1];//动态规划思想
                else if(i != 0 && j != 0 && j != i)
                    a[i][j] += max(a[i-1][j-1], a[i-1][j]);//动态规划思想
            }
        }
    
        i = n-1;
        max1 = a[i][0];
        for(j = 1; j < n; j++){
        
            if(max1 < a[i][j])
                max1 = a[i][j];
        }
        printf("%d\n", max1);
    }
    
    int main()
    {
        scanf("%d", &n);
        sca();
        return 0;
    }
    //不够简洁仍需规范步骤
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 148KB
    Submit time: 2017-01-16 09:20:07
    ****************************************************/

爱好者们可以考虑一下为什么以下两个提交代码仅因为  
/*a\[i\]\[j\] = max(a\[i+1\]\[j\], a\[i+1\]\[j+1\]) + D\[i\]\[j\];*/不同而提交结果不同，  
希望留言评论探讨自己的想法，谢谢！

/***************************************************
    User name: jk160630
    Result: Wrong Answer
    Take time: 0ms
    Take Memory: 120KB
    Submit time: 2017-01-16 10:31:25
    ****************************************************/
    
    #include <stdio.h>
    #define max(a, b) (a > b)? a: b
    
    int a[104][104], D[104][104], n;
    
    void sca();
    
    int main()
    {
        scanf("%d", &n);
        sca();
        return 0;
    }
    
    void sca()
    {
        int i, j;
        for(i = 0; i < n; i++)
        {
        
            for(j = 0; j <= i; j++)
            {
        
                scanf("%d", &D[i][j]);
            }
        }
        for(i = n-1; i >= 0; i--)
        {
        
            for(j = 0; j <= i; j++)
            {
        
                if(i == n-1)
                    a[i][j] = D[i][j];
                else
                {
        
                    a[i][j] = max(a[i+1][j], a[i+1][j+1]) + D[i][j];
                }
            }
        }
        printf("%d\n", a[0][0]);
    }

/***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-01-16 10:40:53
    ****************************************************/
    #include <stdio.h>
    #define max(a, b) (a > b)? a: b
    
    int a[104][104], D[104][104], n;
    
    void sca();
    
    int main()
    {
        scanf("%d", &n);
        sca();
        return 0;
    }
    
    void sca()
    {
        int i, j, t;
        for(i = 0; i < n; i++)
        {
        
            for(j = 0; j <= i; j++)
            {
        
                scanf("%d", &D[i][j]);
            }
        }
        for(i = n-1; i >= 0; i--)
        {
        
            for(j = 0; j <= i; j++)
            {
        
                if(i == n-1)
                    a[i][j] = D[i][j];//动态规划
                else
                {
        
                    t = max(a[i+1][j], a[i+1][j+1]);
                    a[i][j] = t + D[i][j];//动态规划（减少对重复子问题的运算）
                }
            }
        }
        printf("%d\n", a[0][0]);
    }
    //动态规划 / (自底而上)

[SouthEast]: /images/20220711/6febb8c23dd7448d9529fc591c2058ff.png