如何求解三角形中奇偶数量相等的最大路径和

路径上奇数、偶数数量完全相等，前提一定是路径经过的总元素个数为偶数——总长度是奇数的话，根本没法把元素拆成数量相等的两类奇偶数。

你举的示例里，走到第4行（行号从0开始计数）的路径长度是4，是偶数，具备满足条件的基础；如果走到第5行，路径长度是5，是奇数，天生不可能满足奇偶相等，这也是示例里为什么不把最后一行纳入路径的核心原因。
你之前熟悉的传统自底向上DP，只记录「到达某个位置的最大路径和」，缺失了「当前路径累计了多少个奇数、多少个偶数」的关键信息，自然没法判断后续走下去能不能凑到两类数量相等。解决方法很直接：在原有DP状态上多加一个维度，记录当前路径的奇偶数量差值，就能把约束完整纳入计算。

状态设计 #

我们不需要同时记录奇数个数、偶数个数两个值，只要记录两者的差值d就行：
d = 当前路径的奇数个数 - 当前路径的偶数个数
当d=0的时候，就意味着两类元素数量完全相等，正好符合题目的要求。

考虑三角形总行数为n时，最长路径最多经过n个元素，此时d的最大可能值是n（全奇数），最小可能值是-n（全偶数），整个状态的规模是完全可控的，不会出现爆炸式增长。
具体的DP状态定义为：
dp[i][j][d] 表示从位置(i,j)（i是行号，j是该行内的元素位置）出发，走到三角形底边的所有路径中，累计差值为d时，能拿到的最大路径和。

实际存储时为了避免d为负数导致数组下标异常，可以给所有d值加一个大小为n的偏移量，把下标范围映射到0~2n的合法区间。

递推逻辑 #

完全沿用你熟悉的自底向上计算顺序：

• 初始化最底层状态
  对最后一行（第n-1行）的每个元素：
  • 如果当前元素是奇数：从这个点出发的最短路径（仅自身）的差值为1（1个奇数、0个偶数），对应的最大和就是元素本身的值，即dp[n-1][j][1] = triangle[n-1][j]
  • 如果当前元素是偶数：对应的差值为-1（0个奇数、1个偶数），即dp[n-1][j][-1] = triangle[n-1][j]
• 向上逐行递推
  对第i行的每个位置j，先算当前元素对差值的贡献值c：如果是奇数c=+1，如果是偶数c=-1。
  因为从(i,j)出发只能走到下一行的j位置或者j+1位置，所以所有路径的和都是「当前元素值 + 下一行相邻位置出发的某条路径的和」。我们遍历下一行所有可能的差值状态：
  • 若从下一行同位置(i+1,j)出发的路径差值为d1，加上当前贡献c后，新的差值为d = d1 + c，对应的路径和为 triangle[i][j] + dp[i+1][j][d1]
  • 若从下一行右下位置(i+1,j+1)出发的路径差值为d2，加上当前贡献c后，新的差值为d = d2 + c，对应的路径和为 triangle[i][j] + dp[i+1][j+1][d2]
    对同一个新差值d，取上面两种情况里更大的数值，作为dp[i][j][d]的结果即可。

结果获取 #

三角形的起点是(0,0)，我们要找的就是从这个起点出发、差值d=0时的最大路径和，也就是dp[0][0][0]。拿题目给出的示例三角形计算，这个值就是5+6+13+14=38，和示例的返回结果完全一致。

兼容特殊路径情况 #

你之前尝试推导时遇到的特殊路径（比如[奇,奇,奇,偶,偶,偶]），在这个状态体系里是完全可以被捕捉的：它的差值变化是1→2→3→2→1→0，最终会落在d=0的状态里，根本不需要做「每两行凑一个奇偶」的不合理假设，不管差值怎么波动，只要最终能回到0，就能被纳入计算。

复杂度说明 #

这种方法的时间复杂度和传统三角形最大路径和处于同一量级，因为每个位置的d值范围是和当前行号线性相关的，总计算量为O(n²)；空间上可以用滚动数组优化，因为计算第i行的状态时，只需要保留第i+1行的dp值，空间占用可以降到O(n)。 #

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