n步骤采取1,2或3步骤.有多少种方法可以达到顶峰？

Question

如果我们有n个步骤并且我们一次可以上升1步或2步,则步数和爬升方式之间存在斐波纳契关系.IF和ONLY,如果我们不计算2 + 1和1 + 2不同.

但是,这不再是这种情况,并且必须添加我们添加第三个选项,采取3个步骤.我该怎么做呢？

是)我有的:

1 step = 1 way
2 steps = 2 ways: 1+1, 2
3 steps = 4 ways: 1+1+1, 2+1, 1+2, 3

我不知道从哪里可以找到n楼梯的路数

我得到7为n = 4和14得到n = 5我通过做它之前的所有组合的总和得到14 + 7 + 4 + 2 + 1.所以n步的方式= n-1种方式+ n-2种方式+ .... 1种方式假设我保留了所有的值.DYNAMIC编程.1 2和3步将是基本情况是正确的？

Answer 1

我会说公式将以下列方式看待:

K(1) = 1
K(2) = 2
k(3) = 4
K(n) = K(n-3) + K(n-2) + K(n - 1)

公式说,为了达到第n步,我们必须首先达到:

• n-3'步骤然后立即采取3步,即K(n-3)
• 或n-2'步骤,然后一次采取2步,即K(n-2)
• 或第n-1步,然后立即采取1步,即K(n-1)

K(4)= 7,K(5)= 13等

您可以使用递归公式或使用动态编程.

Answer 2

Python解决方案:

递归O(n)

这是基于迈克尔的答案.

import functools

@functools.lru_cache(maxsize=None)
def recursive(n):
    if n < 4:
        initial = [1, 2, 4]
        return initial[n-1]
    else:
        return recursive(n-1) + recursive(n-2) + recursive(n-3)

递归O(log(n))

这是对这个答案的评论.此tribonacci -by加倍溶液是类似于斐波纳契逐倍增溶液中的算法由Nayuki.请注意,乘法具有比常数更高的复杂度.

def recursive_doubling(n):
    def recursive_tribonacci_tuple(n):
        """Return the n, n+1, and n+2 tribonacci numbers for n>=0.

        Tribonacci forward doubling identities:
        T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
        T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
        T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))
        """
        assert n >= 0
        if n == 0:
            return 0, 0, 1  # T(0), T(1), T(2)

        a, b, c = recursive_tribonacci_tuple(n // 2)
        x = b*b + a*(2*(c - b) - a)
        y = a*a + b*(2*c - b)
        z = c*c + b*(2*a + b)

        return (x, y, z) if n % 2 == 0 else (y, z, x+y+z)
    return recursive_tribonacci_tuple(n)[2]  # Is offset by 2 for the steps problem.

迭代O(n)

这是由太极者无极而生的答案推动的.它是迭代斐波纳契解的一个改进的tribonacci扩展.它是从tribonacci修改的,因为它返回c,而不是a.

def iterative(n):
    a, b, c = 0, 0, 1
    for _ in range(n):
        a, b, c = b, c, a+b+c
    return c

迭代O(log(n))(从左到右)

这是对这个答案的评论.这种修改的迭代tribonacci-by-doubleling解决方案来自相应的递归解决方案.有些背景,请看这里和这里.它是从tribonacci修改的,因为它返回c,而不是a.请注意,乘法具有比常数更高的复杂度.

比特n从左到右迭代,即MSB到LSB.

def iterative_doubling_l2r(n):
    """Return the n+2 tribonacci number for n>=0.

    Tribonacci forward doubling identities:
    T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
    T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
    T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))
    """
    assert n >= 0
    a, b, c = 0, 0, 1  # T(0), T(1), T(2)
    for i in range(n.bit_length() - 1, -1, -1):  # Left (MSB) to right (LSB).
        x = b*b + a*(2*(c - b) - a)
        y = a*a + b*(2*c - b)
        z = c*c + b*(2*a + b)
        bit = (n >> i) & 1
        a, b, c = (y, z, x+y+z) if bit else (x, y, z)
    return c

笔记:

• list(range(m - 1, -1, -1)) == list(reversed(range(m)))
• 如果该位是奇数(1),则序列前进一次迭代.在对有效整数求幂问题理解相同之后,这直观有意义.

迭代O(log(n))(从右到左)

这是对这个答案的评论.比特n从右到左迭代,即LSB到MSB.这种方法可能不是规定性的.

def iterative_doubling_r2l(n):
    """Return the n+2 tribonacci number for n>=0.

    Tribonacci forward doubling identities:
    T(2n)   = T(n+1)^2 + T(n)*(2*T(n+2) - 2*T(n+1) - T(n))
    T(2n+1) = T(n)^2 + T(n+1)*(2*T(n+2) - T(n+1))
    T(2n+2) = T(n+2)^2 + T(n+1)*(2*T(n) + T(n+1))

    Given Tribonacci tuples (T(n), T(n+1), T(n+2)) and (T(k), T(k+1), T(k+2)),
    we can "add" them together to get (T(n+k), T(n+k+1), T(n+k+2)).

    Tribonacci addition formulas:
    T(n+k)   = T(n)*(T(k+2) - T(k+1) - T(k)) + T(n+1)*(T(k+1) - T(k)) + T(n+2)*T(k)
    T(n+k+1) = T(n)*T(k) + T(n+1)*(T(k+2) - T(k+1)) + T(n+2)*T(k+1)
    T(n+k+2) = T(n)*T(k+1) + T(n+1)*(T(k) + T(k+1)) + T(n+2)*T(k+2)
    When n == k, these are equivalent to the doubling formulas.
    """
    assert n >= 0
    a, b, c = 0, 0, 1  # T(0), T(1), T(2)
    d, e, f = 0, 1, 1  # T(1), T(2), T(3)
    for i in range(n.bit_length()):  # Right (LSB) to left (MSB).
        bit = (n >> i) & 1
        if bit:
            # a, b, c += d, e, f
            x = a*(f - e - d) + b*(e - d) + c*d
            y = a*d + b*(f - e) + c*e
            z = a*e + b*(d + e) + c*f
            a, b, c = x, y, z
        # d, e, f += d, e, f
        x = e*e + d*(2*(f - e) - d)
        y = d*d + e*(2*f - e)
        z = f*f + e*(2*d + e)
        d, e, f = x, y, z
    return c

约稿

近似当然主要用于非常大的n.使用取幂操作.注意,取幂具有比常数更高的复杂度.

def approx1(n):
    a_pos = (19 + 3*(33**.5))**(1./3)
    a_neg = (19 - 3*(33**.5))**(1./3)
    b = (586 + 102*(33**.5))**(1./3)
    return round(3*b * ((1./3) * (a_pos+a_neg+1))**(n+1) / (b**2 - 2*b + 4))

的近似上述测试是正确的,直到N = 53,在这之后是不同的.使用更高精度的浮点运算肯定有可能在实践中得到更好的近似.

def approx2(n):
    return round((0.618363 * 1.8392**n + \
                  (0.029252 + 0.014515j) * (-0.41964 - 0.60629j)**n + \
                  (0.029252 - 0.014515j) * (-0.41964 - 0.60629j)**n).real)

的近似上述测试是正确的,直到N = 11,在这之后是不同的.

Answer 3

也许它只是 2^(n-1)，其中 n 是步数？

这对我来说很有意义，因为只需 4 个步骤，就有 8 种可能性：

4,
3+1,
1+3,
2+2,
2+1+1,
1+2+1,
1+1+2,
1+1+1+1,

我想这就是模式