小编Jef*_*rry的帖子

我一直在研究这个问题。

• 目标是用砖建造楼梯
• 有 N 块砖，必须全部用来建造楼梯
• 楼梯由不同尺寸的台阶按严格递增的顺序组成
• 楼梯间不允许有相同尺寸的台阶
• 每个楼梯至少由两个台阶组成，每个台阶至少包含一块砖

完整问题的链接http://acm.timus.ru/problem.aspx?num=1017&locale=en

我已经知道这是处理不同的分区和数论/背包问题。目标是有效地给出一个列表 n = [1,2,3,....n -1] 确定存在多少个加起来为 N 的无序集合。我说无序是因为给定的列表没有重复项，因此任何组合都可以排序为给定大小的有效特定答案以符合规则。我也理解一般概念是你从高度 1 开始并分支/添加所有可能的组合，直到新的高度超过砖块，并且仅当新高度用完所有剩余的砖块时才添加到总组合中那一点。我意识到有一些模式，就像您在进入 4 时已经知道 n = 3 存在多少个分区一样，因此使用该数据（动态编程）是解决方案的一部分。

我最终找到了以下解决方案。

n = int(input())
m = [[0 for i in range(n + 1)] for j in range(n + 1)]
m[0][0] = 1  # base case

for last in range(1, n + 1):
    for left in range(0, n + 1):
        m[last][left] = m[last - 1][left]
        if left >= last:
            m[last][left] += m[last - 1][left - …