数字三角形问题给定一个数字三角形通常是一个二维数组或类似结构例如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 行有 i1i1 个数。定义dp[i][j]从位置 (i,j) 出发到达最底层的最大路径和状态转移方程自底向上 dp[i][j]a[i][j]max(dp[i1][j], dp[i1][j1])边界条件 dp[n−1][j]a[n−1][j]最后答案 dp[0][0]#includebits/stdc.h using namespace std; int maxSum(vectorvectorint b) { int n b.size(); if (n 0) return 0; // 只需要一维数组存储当前行的dp值 vectorint 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[j1]); } } return dp[0]; } int main(){ vectorvectorint 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 303 8 23 218 1 0 20 13 102 7 4 4 7 12 10 104 5 2 6 5 4 5 2 6 5最大路径和: 30路径: 7 - 3 - 8 - 7 - 5