在使用动态编程的 Python 程序中没有得到预期的输出

Question

我写了这个使用动态规划的程序：

def count_partitions(n, k):
    if n < k:
        return 0
    elif n == k == 3:
        return 1
    else:
        # Initialize table with base cases
        table = [[0] * (k+1) for _ in range(n+1)]
        table[3][3] = 1

        # Fill in table using recurrence relation
        for i in range(4, n+1):
            for j in range(3, k+1):
                table[i][j] = (j-2) * table[i-1][j] + (j-1) * table[i-1][j-1]

        return table[n][k]

我的代码运行了，但没有得到预期的结果。我希望这些输出：

# Outputs 1, should output 3
count_partitions(4, 3)
# Outputs 1, should output 9
count_partitions(5, 3)
# Outputs 21, should output 37
count_partitions(6, 4)

Answer 1

由于您没有提供问题的描述，我们无法帮助您找到正确的解决方案，但我们可以让您开始了解为什么您当前的程序会这样运行。

最简单的是输入

n=4, k=3

，输出

1

。这是因为你像这样初始化表：

    table = [[0] * (k+1) for _ in range(n+1)]
    table[3][3] = 1

所以你的表，在这个执行之后将是一个 5x4 的 0 矩阵，除了位置

[3,3]

，这是 1：

# k=0 1 2 3
  [ 0 0 0 0 ] # n=0
  [ 0 0 0 0 ] #   1
  [ 0 0 0 0 ] #   2
  [ 0 0 0 1 ] #   3
  [ 0 0 0 0 ] #   4

然后你的循环从

i=4

（在n轴）和

j=3

（在k轴）开始。它也停在

i=4, j=3

。

for i in range(4, n+1):
    for j in range(3, k+1):

然后计算单个值（因为循环只运行一次）：

# i=4, j=3
# table[3][3] = 1
# all other table[x][y] = 0

table[i][j] = (j-2) * table[i-1][j] + (j-1) * table[i-1][j-1]

# This reduces to
table[4][3] = 1 * 1 + 2 * 0 = 1

然后您返回

table[n][k]

，再次使用

n=4, k=3

，所以这将返回1，这是在循环中设置的。

您需要做的是查看此示例发生的情况，并解释 应该 发生的情况。也许在解释中，你会发现问题。