algorithm - 自定义步长间隔的楼梯问题

Question

我理解经典的楼梯问题，您可以走 1 次、2 次或 3 次，并显示您可以到达第 n 步的独特方式。但是我被要求允许用户输入他们希望的任何间隔步骤以及楼梯的大小。例如楼梯大小为 10，间隔为 {1,3,5}。我正在努力理解在概念层面完成此任务所需的算法，我们将不胜感激任何帮助。

Answer 1

创建一个大小为 N 的数组，其中 arr[i] 表示从第一步到第 i'th 步的方法数。

任何步骤 i 和 step_array 之间的关系是:-

for step in step_array:
    arr[i]=arr[i]+arr[i-step]

您必须为 i 的每个值重复此操作。

为什么会这样？

假设您当前在步骤 i 并且允许的步骤是 [2,6,19]

您之前的步骤可能是什么？

因为只允许出现在 step_array 中的那些步骤，所以你一定是在:-

i-2
i-6
i-19

因为只有这些步骤才能一步到位。