基于Python的三项式系数动态规划实现疑问

我尝试用动态规划方法生成三项式系数三角形，已经搭建好三角形的结构（每行元素数量为2*行号+1，行号从0开始），但无法编写计算真实系数值的代码，目前用占位符替代。我知道行中间值为上一行忽略两侧1的总和，也了解相关递推公式，但不知道如何转化为代码。

现有代码 #

def Trinomial_Triangle(Number_of_Rows):
    Triangle = [[1]]
    Length_of_Row = 1

    for Outer_Index in range(Number_of_Rows - 1):

        Temporary_Array = [0] + Triangle[Outer_Index] + [0]
        print("Temporary Array", Temporary_Array)
        Length_of_Row += 2
        Values_in_Row = []

        for First_Inner_Index in range(Length_of_Row):

            Value = Triangle[Outer_Index][0]

            Values_in_Row.append(Value)
        Triangle.append(Values_in_Row)
    return Triangle


print(Trinomial_Triangle(5))

三项式系数示意图 #

递推逻辑说明 #

三项式系数的核心递推关系为：当前行的任意元素 = 上一行中左上方、正上方、右上方三个元素的和。为了避免边界索引越界，我们给上一行的首尾各补一个0，这样每个位置都能直接取到三个相邻元素进行求和。

修正后的代码 #

def Trinomial_Triangle(Number_of_Rows):
    Triangle = [[1]]
    for _ in range(Number_of_Rows - 1):
        prev_row = Triangle[-1]
        # 给上一行首尾补0，处理边界元素的计算
        padded_prev = [0] + prev_row + [0]
        current_row = []
        # 当前行长度 = 上一行长度 + 2
        for i in range(len(padded_prev) - 2):
            # 取三个相邻元素的和
            val = padded_prev[i] + padded_prev[i+1] + padded_prev[i+2]
            current_row.append(val)
        Triangle.append(current_row)
    return Triangle

# 测试：生成5行三项式系数三角形
print(Trinomial_Triangle(5))

代码解释 #

1. 初始化：从只有一个元素[1]的三角形开始，对应第0行。
2. 补0处理：每次循环给上一行的首尾各添加一个0，确保边界元素可以正常取到三个相邻值（不存在的位置用0代替）。
3. 生成当前行：遍历补0后的上一行，每次取连续三个元素的和作为当前行的元素，最终当前行的长度会比上一行多2，符合预设的结构。
4. 返回结果：循环结束后返回完整的三项式系数三角形。

运行上述代码后，输出的5行三项式系数三角形为：

[[1], [1, 1, 1], [1, 2, 3, 2, 1], [1, 3, 6, 7, 6, 3, 1], [1, 4, 10, 16, 19, 16, 10, 4, 1]]

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