第九章-数字三角形

数字三角形问题

给定一个数字三角形（通常是一个二维数组或类似结构），例如：

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

你从顶部出发，每次可以向下走左下或右下的相邻数字，到达底部，求出从顶部到底部的路径上数字之和的最大值。

解：

设三角形有 nn 行，用 a[i][j]a[i][j] 表示第 ii 行、第 jj 列的数字（从 0 开始计数，且第 ii 行有 i+1i+1 个数）。

定义：dp[i][j]=从位置 (i,j) 出发到达最底层的最大路径和

状态转移方程（自底向上）： dp[i][j]=a[i][j]+max⁡(dp[i+1][j], dp[i+1][j+1])

边界条件： dp[n−1][j]=a[n−1][j]

最后答案 = dp[0][0]

#include<bits/stdc++.h> using namespace std; int maxSum(vector<vector<int>>& b) { int n = b.size(); if (n == 0) return 0; // 只需要一维数组存储当前行的dp值 vector<int> dp(b[n-1].begin(), b[n-1].end()); // 自底向上更新 for (int i = n-2; i >= 0; i--) { for (int j = 0; j <= i; j++) { dp[j] = b[i][j] + max(dp[j], dp[j+1]); } } return dp[0]; } int main(){ vector<vector<int>> a = { {7}, {3, 8}, {8, 1, 0}, {2, 7, 4, 4}, {4, 5, 2, 6, 5} }; // 最大路径和 int max = maxSum(a); cout << "最大路径和: " << max << endl; }

三角形： DP表：
7 30
3 8 23 21
8 1 0 20 13 10
2 7 4 4 7 12 10 10
4 5 2 6 5 4 5 2 6 5

最大路径和: 30
路径: 7 -> 3 -> 8 -> 7 -> 5