IOI 1994 洛谷1216 数字三角形问题解析,C++动态规划实现详解

问题描述与基本分析

洛谷1216题是一个经典的数字三角形问题，给定一个由数字组成的三角形，要求从顶部到底部的路径中，使路径上数字总和达到最大。每个节点只能移动到其左下方或右下方的节点。这个问题看似简单，但蕴含着动态规划(DP)的典型特征，非常适合用来理解DP的基本思想。

为什么说这个问题适合用动态规划解决？问题具有最优子结构性质——全局最优解包含局部最优解。存在重叠子问题——不同路径会经过相同的节点。通过分析可以发现，暴力解法的时间复杂度高达O(2^n)，而动态规划能将其优化到O(n^2)。

动态规划状态定义

定义dp[i][j]表示从第i行第j个元素出发到底部的最大路径和。这种自底向上的状态定义是解决数字三角形问题的关键。状态转移方程可以表示为：dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]。

如何理解这个状态转移方程？对于三角形中的任意一个位置(i,j)，它只能移动到下一行的相邻位置。因此，当前位置的最大值等于下一行相邻两个位置的最大值加上当前位置的值。这种定义方式避免了递归带来的重复计算问题。

递推实现与空间优化

从状态转移方程出发，我们可以采用两种实现方式：自顶向下的记忆化搜索和自底向上的递推。后者通常更高效且易于实现。在实际编码中，可以直接在原数组上操作，将空间复杂度从O(n^2)优化到O(1)。

让我们看一个具体案例：对于三角形[[7],[3,8],[8,1,0],[2,7,4,4]]，自底向上的计算过程是怎样的？初始化一行，逐层向上计算。第三行的8会取max(2,7)+8=15，1会取max(7,4)+1=8。这种计算方式确保了每个位置只计算一次。

C++完整实现代码

int main() {
    int n;
    cin >> n;
    vector> triangle(n, vector(n));
    // 读取数字三角形
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    // 初始化dp数组
    vector> dp = triangle;
    // 自底向上递推
    for(int i = n-2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
        }
    }
    cout << dp[0][0] << endl;
    return 0;
}

算法优化与变种思考

上述基础解法已经能AC洛谷1216题，但我们可以进一步思考优化空间。实际上只需要O(n)的额外空间，即使用一维数组存储当前行的计算结果。每次计算时覆盖前一行的结果，这种优化在大型数据场景下尤为重要。

这个问题的变种也值得思考：如果要求输出具体路径而不仅是最大值，该如何修改代码？可以额外维护一个path数组记录选择路径。或者如果允许从任意位置开始，又该如何调整状态定义？这些思考能帮助深入理解动态规划的应用场景。

数字三角形问题是动态规划的入门经典，通过分析其最优子结构和重叠子问题特性，我们实现了时间复杂度O(n^2)的解法。C++实现展示了自底向上的递推过程，清晰的注释帮助理解DP的核心思想。掌握这个问题能为解决更复杂的动态规划问题打下坚实基础。