求三角形顶至底最大和的时空复杂度及给定算法的最优最差复杂度

首先，先明确你给出的算法逻辑：通过动态规划的方式逐行计算每个位置的最大路径和，每个位置的取值依赖于上一行的相邻位置（首尾元素仅依赖上一行的首尾元素）。

时间复杂度 #

不管是最优情况还是最差情况，时间复杂度都是O(n²)，其中n是三角形的行数：

• 算法需要遍历三角形中的每一个元素，第1行有1个元素，第2行有2个元素……第n行有n个元素，总元素数是 1+2+…+n = n(n+1)/2，这个量级等价于O(n²)。
• 每个元素的处理逻辑都是常数时间：要么做简单的加法，要么做一次比较后加法，没有嵌套循环或递归带来的额外开销，单元素处理时间为O(1)。
• 不存在能跳过部分元素的场景，所有元素都必须被计算，因此最优与最差时间复杂度完全一致。

空间复杂度 #

按照你给出的实现方式，空间复杂度是O(n²)：

• 我们需要维护一个和原三角形规模完全一致的二维数组MAX_SUM，用来存储每个位置的最大路径和，空间开销与元素总数相同，即O(n²)。

额外优化：空间复杂度可降至O(n) #

如果对空间做优化，其实不需要完整的二维数组：计算第i行元素时，仅需依赖第i-1行的结果。我们可以用一个一维数组，每次迭代覆盖更新当前行的结果，这样空间复杂度就能优化到O(n)——比如用长度为n的数组，从上到下或从下到上更新，每次仅保留上一行的状态。

内容的提问来源于stack exchange，提问作者dhamini poornachandra