数字三角形

ゝ一世哀愁。 2024-03-30 01:33 62阅读 0赞

## 数字三角形 ##

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

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

输入格式  
第一行包含整数 n，表示数字三角形的层数。

接下来 n 行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式  
输出一个整数，表示最大的路径数字和。

数据范围  
1≤n≤500,  
−10000≤三角形中的整数≤10000  
输入样例：  
5  
7  
3 8  
8 1 0  
2 7 4 4  
4 5 2 6 5  
输出样例：  
30

### 思路 ###

![在这里插入图片描述][e375e05000dd450f87f9b865e6e8d10e.png]  
状态表示：`f(i,j)`

*  集合：从`(i,j)`到最后一层的所有方案
 *  属性：`Max`

状态计算

*  这条路径可以从`(i+1,j)`走上来，即`f(i+1,j)+ai`
 *  也可以从`(i+1,j+1)`走上来，即`f(i+1,j)+ai,j`
 *  所以状态转移方程就是`f(i,j)=max{fi+1,j,fi+1,j+1}+ai`

答案：

*  根据定义，答案就是`f(1,1)`

### 提交代码 ###

c++版本

#include<iostream>
    using namespace std;
    
    const int N = 1010;
    int f[N][N];
    int n;
    
    int main()
    {
        
        cin >> n;
        for (int i = 1; i <= n; ++ i)
        {
        
            for (int j = 1; j <= i; ++ j)
            {
        
                scanf("%d", &f[i][j]);
            }
        }
        for (int i = n - 1; i >= 1; -- i)
        {
        
            for (int j = n - 1; j >= 1; -- j) // for (int j = 1; j <= i; ++ j) 也可以 但是要慢一些
            {
        
                f[i][j] += max(f[i + 1][j + 1], f[i + 1][j]);
            }
        }
        cout << f[1][1];
        return 0;
    }

思路：  
这道题我认为最容易错的点就是边界问题，并且如果是JAVA，容易有溢出问题。

一般就是就是向下走，和向上爬两种思路，向上爬的思路可以不需要考虑边界问题。

而当向下走的时候，需要考虑边界问题。也就是对于f\[2\]\[1\]的时候，f\[1\]f\[0\]并没有设置这个值，默认为0，题中的数字有负数，则会出现错误的最大值。需要对于f进行重置，置为Integer.MIN\_VALUE.

JAVA中最最容易错的点  
：如果f\[i\]\[j\]= Math.max(f\[i - 1\]\[j - 1\] + a\[i\]\[j\], f\[i - 1\]\[j\] + a\[i\]\[j\])其中的f\[i - 1\]\[j - 1\]如果为Integer.MIN\_VALUE,并且a\[i\]\[j\] = 负数时候，会溢出！！！需要写成 Math.max(f\[i - 1\]\[j - 1\] + f\[i - 1\]\[j\]);

Java版本

import java.util.Scanner;
    
    public class Main {
        
        public static void main (String[] args) {
        
            int[][] a = new int[510][510];
            int[][] f = new int[510][510];
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            for (int i = 1; i <= n; i ++) {
        
                for (int j = 1; j <= i; j++) {
        
                    a[i][j] = sc.nextInt();
                }
            }
    
            for (int i = n; i >= 1; i--) {
        
            //从最后一排开始走，从下往上。
                for (int j = 1; j <= i; j++) {
        
                    f[i][j] = Math.max(f[i + 1][j + 1], f[i + 1][j]) + a[i][j];
                }
            }
    
            System.out.println(f[1][1]);
        }
    }

思路：  
状态表示：dp\[i\]\[j\]dp\[i\]\[j\]表示到ijij的数值最大值；  
状态计算：dp\[i\]\[j\]=v\[i\]\[j\]+max(dp\[i−1\]\[j−1\],dp\[i−1\]\[j\])

Python版本

n = int(input())
    v = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        in_ = list(map(int, input().split()))
        v[i][1:len(in_) + 1] = in_
    
    INF = 10001
    dp = [[-INF for _ in range(n + 1)] for _ in range(n + 1)]
    dp[1][1] = v[1][1]
    for i in range(2, n + 1):
        for j in range(1, i + 1):
            dp[i][j] = v[i][j] + max(dp[i - 1][j - 1], dp[i - 1][j])
    print(max(dp[n][1:]))

[e375e05000dd450f87f9b865e6e8d10e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9bb00ff6ed4b4c4ca96aab161202c901.png