编程挑战：这个算法（与数论相关）如何工作？

Question

为了提高我的 python 技能，我有时会在互联网上进行各种挑战（例如在 hackerrank 上）。谷歌搜索其他东西，我发现了这个问题，以及互联网上的随附解决方案，它引起了我的注意：

其中最宏伟的楼梯

随着 LAMBCHOP 末日装置的完成，拉姆达指挥官正在为她在银河舞台上的首次亮相做准备 - 但为了华丽的登场，她需要一个宏伟的楼梯！作为她的私人助理，你的任务是弄清楚如何建造有史以来最好的楼梯。

Lambda 为您提供了可用积木类型的概述以及预算。您可以购买不同数量的不同类型的砖块（例如，3 个粉色小砖块或 5 个蓝色花边砖块）。拉姆达指挥官想知道每块砖块可以建造多少种不同类型的楼梯，这样她就可以选择选项最多的那个。

每种类型的楼梯应包含 2 个或更多台阶。不允许有两个台阶处于相同高度 - 每个台阶必须低于前一个台阶。所有台阶必须至少包含一块砖块。台阶的高度被分类为组成该台阶的砖块的总数。例如，当N = 3时，您只有1种选择如何建造楼梯，第一步的高度为2，第二步的高度为1：（#表示一块砖）

#
##
21

当 N = 4 时，你仍然只有 1 个楼梯选择：

#
#
##
31

但是当 N = 5 时，有两种方法可以用给定的砖块建造楼梯。两个楼梯的高度可以为 (4, 1) 或 (3, 2)，如下所示：

#
#
#
##
41

#
##
##
32

编写一个名为answer(n) 的函数，该函数采用正整数n 并返回可以用n 块砖建造的不同楼梯的数量。n 永远至少为 3（这样你就可以有一个楼梯），但不能超过 200，因为 Lambda 指挥官不是有钱人！

https://en.wikipedia.org/wiki/Partition_(number_theory)

def answer(n):
    # make n+1 coefficients
    coefficients = [1]+[0]* n
    #go through all the combos
    for i in range(1, n+1):
        #start from the back and go down until you reach the middle
        for j in range(n, i-1, -1):
            print "add", coefficients[j-i], "to position", j
            coefficients[j] += coefficients[j-i]
            print coefficients
    return coefficients[n] - 1

现在我尝试通过手动示例来理解上述解决方案。例如，对于

answer(10)

选项有：

1 2 3 4
1 2 7
1 3 6
1 9
1 4 5
2 3 5
2 8
3 7
4 6

所以总共有 9 个选项，加起来就是 10 个。当我运行该程序时，最后的几个列表是：

        add 1 to position 10
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 7, 9]
        add 1 to position 9
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 9]
        add 1 to position 10
        [1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10]

        9

所以结果是正确的，但我不明白最终列表或所有列表与解决方案有什么关系。我尝试阅读有关数论的链接，但这更令人困惑，我认为维基百科条目不是为第一次遇到此问题类型的人编写的。

有人可以引导我解决这个问题吗？该算法是如何工作的？

Answer 1

关于您发布的答案功能：

在外循环的每次迭代结束时，是在使用了总共​​的块后，coefficients[x]最多可以制作高度为 的楼梯数量。（包括只有一级楼梯或零级楼梯的楼梯）。ix

coefficients初始化为[1,0,0...]循环之前，表示你只能建造一个高度最多为 0 的楼梯。这是一个没有楼梯的楼梯，所以你将消耗 0 个方块来建造它。

在循环的每次迭代中，系数数组从表示 max height 转换i-1为表示 max height i，通过合并向任何较短的楼梯添加高度步骤的可能性i，从而至少留下i块。

最后，它返回使用所有块后可以到达终点的方法数n，减一，因为单个楼梯的高度n无效。

该算法是“动态规划”的一个例子。