Python实现分拆数三角字典的问题求助

我正在尝试构建一个对应分拆数三角的字典，想要复现（下划线红色标注的）递推关系，最终得到这样的结果：

{0: [1], 1: [1, 1], 2: [1, 1, 1], 3: [1, 2, 1, 1], 4: [1, 2, 2, 1, 1], 5: [1, 3, 3, 2, 1, 1]}
（我尝试让键等于n，但没能成功）

以下是我的代码：

dic1 = {}
for n in range(0,6):
    dic1[n] = [1]
    for i in range(0, 6):
        if n > 0 and i > 0:
            if i > n:
                continue
            elif n - i < i:
                dic1[n].append(dic1[n-1][i-1])
            else:
                dic1[n].append(dic1[n-1][i-1] + dic1[n-i][i])
print(dic1)

这段代码输出的结果是：

{0: [1], 1: [1, 1], 2: [1, 2, 1], 3: [1, 3, 2, 1], 4: [1, 4, 4, 2, 1], 5: [1, 5, 6, 4, 2, 1]}

我实在找不到哪里出错了，求各位帮忙看看，谢谢！

问题分析与修正方案 #

嘿，我帮你找到了问题所在！你用错了递推式中要调用的列表项，而且循环的初始化方式也需要调整。

你想要实现的递推关系，正确的逻辑应该是：

• 对于每个n，列表的第i项（从0开始）：
  • 第0项固定为1，第n项也固定为1
  • 当1 ≤ i < n时：
    • 如果n - i < i（也就是无法再从n中分出一个i大小的部分），那么当前值等于dic1[n-1][i]（即n-1的第i项）
    • 否则，当前值等于dic1[n-1][i] + dic1[n-i][i-1]（即n-1的第i项加上n-i的第i-1项）

而你原来的代码错误地使用了dic1[n-1][i-1]和dic1[n-i][i]，导致计算出的数值偏大，不符合目标结果。另外，直接初始化[1]后追加元素的方式，容易出现索引逻辑混乱的问题，提前初始化对应长度的列表会更清晰。

修正后的代码 #

dic1 = {}
# 初始化n=0的情况
dic1[0] = [1]

for n in range(1, 6):
    # 初始化长度为n+1的列表，默认值0
    dic1[n] = [0] * (n + 1)
    dic1[n][0] = 1  # 第0项固定为1
    dic1[n][n] = 1  # 第n项固定为1
    
    for i in range(1, n):
        if n - i < i:
            # 无法再取i大小的部分，继承n-1的第i项
            dic1[n][i] = dic1[n-1][i]
        else:
            # 递推计算：n-1的第i项 + n-i的第i-1项
            dic1[n][i] = dic1[n-1][i] + dic1[n - i][i - 1]

print(dic1)

运行这段代码后，你就能得到想要的结果：

{0: [1], 1: [1, 1], 2: [1, 1, 1], 3: [1, 2, 1, 1], 4: [1, 2, 2, 1, 1], 5: [1, 3, 3, 2, 1, 1]}

内容来源于stack exchange