时间戳

首页 > 解决方案 > 自定义步长间隔的楼梯问题

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

问题描述

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

标签： algorithm

解决方案

我今天花了相当长的时间来理解这个问题。希望我能解释一下。我将尝试用一个我认为会让它更容易理解的例子来解释。

For example if step sizes are: [1,3,5]
n = number of stairs
n(0) = 1 way, to be at the same position it will be 1 way
n(1) = [1] = 1 
n(2) = [1,1] = 1
n(3) = [1,1,1] , [3] = 2 ways
n(4) = [1,1,1,1] , [1,3] , [3,1] = 3 ways
n(5) = [1,1,1,1,1] , [1,1,3] , [1,3,1] , [3,1,1] , [5] = 5 ways
n(6) = [1,1,1,1,1,1] , [1,1,1,3] , [1,1,3,1] , [1,3,1,1] , [3,1,1,1] , [3,3] , [1,5] , [5,1] = 8 ways

now if we look closely, n(6) can be achieved in 3 ways:
1. taking 1 step first
2. taking 3 step first
3. taking 5 step first

so other way to write n(6) would be:
n(6) = [1,1,1,1,1,1] , [1,1,1,3] , [1,1,3,1] , [1,3,1,1] , [1,5]   >> 1st step is 1
       [3,1,1,1] , [3,3]                                           >> 1st step is 3
       [5,1]                                                       >> 1st step is 5

所以我们可以说：

n(6) = 1st step is 1 + {[1,1,1,1,1] , [1,1,3] , [1,3,1] , [3,1,1] , [5]} >> 1+n(5) 
       1st step is 3 + {[1,1,1] , [3]}                                   >> 3+n(3)
       1st step is 5 + {[1]}                                             >> 5+n(1)

那是：

n(6) = n(5) + n(3) + n(1)
or 
n(6) = n(n-1) + n(n-3) + n(n-5)

但是如果 (n-3) 或 (n-5) 变为负数，则不考虑，因为不会采取任何步骤

因此，如果 i 在 [1,3,5] >> 允许的步数中，我们可以说：如果 (ni) > 0，我们将其添加到计算步数的函数中

或者：for i in [1,3,5] >> steps allowed: if (ni) >= 0 we add the steps

所以如果 n 是 4: 并且 i = [1,3,5] 它将是：

n(4) = n(3) + n(1)

所以上面的步骤也可以写成：

n(0) = 1  
n(1) = 1 
n(2) = n(1) 
n(3) = n(2) + n(0)
n(4) = n(3) + n(1) 
n(5) = n(4) + n(2) + n(0)
n(6) = n(5) + n(3) + n(1)

希望我能解释一下。使用python的解决方案如下：

def simplestairs(n,X):

    if n == 1:
        return 1

    cache = [0 for _ in range(n+1)]
    cache[0] = 1
    cache[1] = 1

    for i in range(2,n+1):
        for x in X:
            if i - x >= 0:
                cache[i] += cache[i-x]

    return cache[-1]

n = 6
X = {1,3,5}

simplestairs(n,X)

推荐阅读