P1216 数字三角形
文章目录
题目信息
| 字段 | 内容 |
|---|---|
| 题号 | P1216 |
| 难度 | 橙题（普及-） |
| 知识点 | 动态规划、记忆化搜索 |
题目描述
观察如下所示的数字三角形：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从顶部（第一行）出发，在每一层可以选择向左下或向右下走（即 (i, j) 只能走到 (i+1, j) 或 (i+1, j+1)）。
找到一条路径，使路径经过的格子中的数字之和最大，输出这个最大值。
输入格式：
第一行一个整数 n，表示数字三角形的行数（1 ≤ n ≤ 1000）。
接下来 n 行，第 i 行有 i 个整数，表示每行的数字（各数字不超过 10000）。
输出格式：
一个整数，表示从顶部到底部的最大路径和。
样例：
输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出
30
样例解释：
最大路径为 7 → 3 → 8 → 7 → 5，和为 7 + 3 + 8 + 7 + 5 = 30。
解题思路
核心思想：动态规划
这道题是**动态规划（Dynamic Programming）**的经典入门题。
动态规划的核心思想：把一个大问题拆成若干小问题，先解决小问题，再用小问题的解推出大问题的解。
方法一：记忆化递归（自顶向下）
从顶部开始，递归地计算每个位置能得到的最大和。递归过程中用数组缓存结果，避免重复计算。
设 dp[i][j] 表示从位置 (i, j) 出发到最底层，能够得到的最大路径和。
递归方程：
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
终止条件：当 i == n（到达最后一行）时，dp[i][j] = triangle[i][j]。
方法二：自底向上递推（更常见）
从最后一行开始，依次向上计算。每一行的每个位置，只需要知道它下方两个位置的最大值即可。
// 从倒数第二行开始，依次向上递推
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1]);
}
}
最后 triangle[1][1] 就是答案。
为什么从下往上递推可行？
因为最后一行没有更深的路径，所以 dp[n][j] = triangle[n][j] 是确定的。
有了最后一行，倒数第二行的每个位置只需要比较它下方两个相邻位置的最大值，再加上自己的值，就得到了从这个位置出发的最大和。
这个过程不断向上重复，直到顶部。
完整代码
C++（记忆化递归）
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1001;
int triangle[MAX_N][MAX_N];
int memo[MAX_N][MAX_N];
int n;
int MaxSumFrom(int row, int col) {
if (memo[row][col] != -1) {
return memo[row][col];
}
if (row == n) {
memo[row][col] = triangle[row][col];
} else {
int left = MaxSumFrom(row + 1, col);
int right = MaxSumFrom(row + 1, col + 1);
memo[row][col] = max(left, right) + triangle[row][col];
}
return memo[row][col];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> triangle[i][j];
memo[i][j] = -1;
}
}
cout << MaxSumFrom(1, 1) << "\n";
return 0;
}
C++（自底向上递推）
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
const int MAX_N = 1001;
int triangle[MAX_N][MAX_N] = {0};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> triangle[i][j];
}
}
// 自底向上递推
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
cout << triangle[1][1] << "\n";
return 0;
}
关键代码讲解
记忆化递归的核心
int MaxSumFrom(int row, int col) {
if (memo[row][col] != -1) {
return memo[row][col]; // 已计算过，直接返回
}
// ... 计算并缓存结果
memo[row][col] = max(left, right) + triangle[row][col];
return memo[row][col];
}
memo 数组用于记录每个位置已经计算过的最大路径和。当递归走到已经计算过的位置时，直接返回缓存结果，避免了大量重复计算。
自底向上递推的核心
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
从倒数第二行开始，每个位置的值变成「自身 + 下方两个相邻位置中的较大值」。这样一层层向上，最终顶部就变成了整个三角形的最大路径和。
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 记忆化递归 | O(n²) | O(n²) |
| 自底向上递推 | O(n²) | O(n²)（可优化到 O(n)） |
两种方法的时间复杂度相同。自底向上递推的空间可以优化到 O(n)，只需要保存最后一行，然后逐行向上更新。
易错点
-
数组下标：本题采用 1-indexed（下标从 1 开始），递归时注意
(i, j)的相邻位置是(i+1, j)和(i+1, j+1)，不是(i+1, j-1)。 -
边界处理：使用自底向上递推时，循环到
j <= i即可，因为第i行恰好有i个元素。 -
初始化：使用记忆化递归时，
memo数组必须初始化为一个不可能的值（如-1），用于标记「未计算过」。
其他语言解法
Python（自底向上递推）
import sys
def main():
data = sys.stdin.read().strip().split()
if not data:
return
it = iter(data)
n = int(next(it))
triangle = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
for j in range(1, i + 1):
triangle[i][j] = int(next(it))
for i in range(n - 1, 0, -1):
for j in range(1, i + 1):
triangle[i][j] += max(triangle[i + 1][j], triangle[i + 1][j + 1])
print(triangle[1][1])
if __name__ == "__main__":
main()
Java（自底向上递推）
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.NoSuchElementException;
public class Main {
private static final class FastScanner {
private final BufferedInputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0;
private int len = 0;
FastScanner() {
in = new BufferedInputStream(System.in);
}
private int readByte() throws java.io.IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) {
return -1;
}
}
return buffer[ptr++];
}
int nextInt() throws java.io.IOException {
int c, sign = 1, res = 0;
do {
c = readByte();
} while (c <= ' ' && c != -1);
if (c == '-') {
sign = -1;
c = readByte();
}
while (c > ' ') {
res = res * 10 + (c - '0');
c = readByte();
}
return res * sign;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner();
int n = fs.nextInt();
int[][] triangle = new int[n + 2][n + 2];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
triangle[i][j] = fs.nextInt();
}
}
for (int i = n - 1; i >= 1; i--) {
for (int j = 1; j <= i; j++) {
triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
System.out.println(triangle[1][1]);
}
}
Go（自底向上递推）
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Split(bufio.ScanWords)
if !scanner.Scan() {
return
}
n, _ := strconv.Atoi(scanner.Text())
const maxN = 1001
triangle := make([][]int, maxN)
for i := 0; i < maxN; i++ {
triangle[i] = make([]int, maxN)
}
for i := 1; i <= n; i++ {
for j := 1; j <= i; j++ {
if scanner.Scan() {
val, _ := strconv.Atoi(scanner.Text())
triangle[i][j] = val
}
}
}
for i := n - 1; i >= 1; i-- {
for j := 1; j <= i; j++ {
triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
}
}
fmt.Println(triangle[1][1])
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
JavaScript（自底向上递推）
'use strict';
const fs = require('fs');
const data = fs.readFileSync('/dev/stdin', 'utf8');
const tokens = data.trim().split(/\s+/).map(Number);
let idx = 0;
const n = tokens[idx++];
const triangle = Array.from({ length: n + 2 }, () =>
Array(n + 2).fill(0)
);
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= i; j++) {
triangle[i][j] = tokens[idx++];
}
}
for (let i = n - 1; i >= 1; i--) {
for (let j = 1; j <= i; j++) {
triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
console.log(triangle[1][1]);