【动态规划】数字三角形

题目

898. 数字三角形

---

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

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

输入格式

第一行包含整数 $n$ ，表示数字三角形的层数。

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

输出格式

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

数据范围

$1 \le n \le 500$ ,
$-10000 \le 三角形中的整数 \le 10000$

输入样例：

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

输出样例：

30

解题

方法一：动态规划

思路

思维过程：

动态规划：

• 状态定义：$dp[i][j]$ 表示所有从 $(1, 1)$ 开始走到 $(i, j)$ 的路径上数字和的最大值。
• 状态转移方程：$dp[i][j] = \max(dp[i-1][j-1] + a[i][j], dp[i-1][j] + a[i][j])$。
• 初始状态：$dp[1][1] = a[1][1]$。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int INF = 0x3f3f3f3f;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[][] tgl = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                in.nextToken();
                tgl[i][j] = (int) in.nval;
            }
        }
        int dp[][] = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++i) Arrays.fill(dp[i], -INF);
        dp[1][1] = tgl[1][1];
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i][j] = Math.max(tgl[i][j] + dp[i - 1][j], tgl[i][j] + dp[i - 1][j - 1]);
            }
        }
        int max = -INF;
        for (int i = 1; i <= n; ++i) max = Math.max(max, dp[n][i]);
        System.out.println(max);
    }
}

优化

边读入边做状态转移：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[][] dp = new int[n][n];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                in.nextToken();
                int curr = (int) in.nval;
                if (i == 0) {
                    dp[i][j] = curr;
                    continue;
                }
                int prev;
                if (j == 0) prev = dp[i - 1][j];
                else if (j == i) prev = dp[i - 1][j - 1];
                else prev = Math.max(dp[i - 1][j], dp[i - 1][j - 1]);
                dp[i][j] = prev + curr;
                if (i == n - 1) {
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        System.out.println(max);
    }
}

#include <iostream>

using namespace std;

const int N = 510;
int n, a[N][N];

int main() {
    scanf("%d", &n);
    int mx = -1e9;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            scanf("%d", &a[i][j]);
            if (i == 0) continue;
            if (j == 0) a[i][j] += a[i - 1][j];
            else if (j == i) a[i][j] += a[i - 1][j - 1];
            else a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
            if (i == n - 1) mx = max(mx, a[i][j]);
        }
    }
    printf("%d\n", mx);
    
    return 0;
}

滚动数组再优化

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[][] dp = new int[2][n];
        int idx = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j <= i; ++j) {
                in.nextToken();
                int curr = (int) in.nval;
                if (i == 0) {
                    dp[idx][j] = curr;
                    continue;
                }
                int prev;
                if (j == 0) prev = dp[idx ^ 1][j];
                else if (j == i) prev = dp[idx ^ 1][j - 1];
                else prev = Math.max(dp[idx ^ 1][j], dp[idx ^ 1][j - 1]);
                dp[idx][j] = prev + curr;
                if (i == n - 1) {
                    max = Math.max(max, dp[idx][j]);
                }
            }
            idx ^= 1;
        }
        System.out.println(max);
    }
}