$$\color{Red}{数字三角形-三种方法-详细题解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

方法1：从上到下的线性DP

import java.util.*;

public class Main{
    static int N = 510, min = -0x3f3f3f3f;
    static int a[][] = new int [N][N];
    static int f[][] = new int [N][N];

    public static void main(String[] args){
        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=0; i<N; i++)   Arrays.fill(f[i], min);
        f[1][1] = a[1][1];
        for(int i=2; i<=n; i++)
            for(int j=1; j<=i; j++)
                f[i][j] = Math.max(f[i-1][j], f[i-1][j-1]) + a[i][j];

        int res = min;
        for(int i=1; i<=n; i++) res = Math.max(f[n][i], res);
        System.out.println(res);
    }
}

Python3

N = 510
a = [[0] * N for i in range(N)]
f = [[-0x3f3f3f3f] * N for i in range(N)]

n = int(input())
for i in range(1, n+1):
    a[i][1:i+1] = map(int, input().split())

#给f[1][1]赋值后，直接从第二行开始进行动态规划
f[1][1] = a[1][1]
for i in range(2, n+1):
    for j in range(1, i+1):
        f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j]

res = -0x3f3f3f3f        
for j in range(1, n+1):
    res = max(res, f[n][j])

print(res)

C++

#include <iostream>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int a[N][N];
int dp[N][N];

int main()
{
    int n;
    cin >> n;
    //数组距离初始化为负无穷，为了防止出现越界到金字塔外，需要前后多开两层
    for(int i=1; i<=n; i++)
        for(int j = 0; j<=i + 1; j++)
        {
            dp[i][j] = -INF;
            if(j>=1 && j<=i)    scanf("%d", &a[i][j]);
        }
    //dp从上到下求值 
    dp[1][1] = a[1][1];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];
    //由于从上到下，需要考虑到底哪个最大的边界条件    
    int res = -INF;
    for(int i=1; i<=n; i++) res = max(res, dp[n][i]);
    cout << res << endl;
    return 0;
}

方法2：从下到上的去除边界判断线性DP

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 510, n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int[][] a = new int[N][N];
    static int[][] f = new int[N][N];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                a[i][j] = Integer.parseInt(str[j-1]);
            }
        }
        for (int i = n; i >= 1; i--) {
            for (int j = i; j >= 1; j--) {
                f[i][j] = Math.max(f[i+1][j], f[i+1][j+1]) + a[i][j];
            }
        }
        System.out.println(f[1][1]);
    }
}

python3

N = 510
a = [[0] * N for i in range(N)]
f = [[0] * N for i in range(N)]

n = int(input())
for i in range(1, n+1):
    a[i][1:i+1] = map(int, input().split())

for i in range(n, 0, -1):
    for j in range(i, 0, -1):
        f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j]

print(f[1][1])

C++

#include <iostream>
using namespace std;

const int N = 510;

int a[N][N], dp[N][N];//dp[i][j]存储对应点到最后一行距离的最大值

int main()
{
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=i; j++)
            scanf("%d", &a[i][j]);
    //从下往上的取值：不需要考虑最后一排谁最大的边界情况
    for(int i=n; i>0; i--)
        for(int j=i; j>=1; j--)
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j];
    cout << dp[1][1];
    return 0;
}