algorithm - 使用动态规划的可能楼梯

Question

对于网址http://acm.timus.ru/problem.aspx?num=1017&locale=en提到的Staircase问题

我们能否在线性时间 O(k) 内解决它，其中 k 是可能的最大步数？我觉得使用以下方法缺少一些逻辑

有什么建议吗？

下面是我实现的代码:

    def answer(n):
        steps = determine_steps(n)
        x = ((n -1) - n/steps) * ((n-2) - n/steps + 1)  #Minimum of two stair case
        for i in range(3, steps):
            x = x * ((n-i)/i)    #Stairs from 3 can go from minimum height 0 to max (n-i)/i
        return x


    def determine_steps(n):
        """Determine no of steps possible"""
        steps = 1;
        while (steps * steps + steps) <= 2 * n:
            steps = steps + 1
        return steps - 1

    #print answer(212)
    print answer(212)

Answer 1

假设，你有一个函数接受 2 个参数，一个 left这是剩下的砖 block 数，另一个是curr这是您所在台阶的当前高度。现在，在任何一步你都有 2 个选择。第一个选项是通过添加更多积木来增加当前台阶的高度，即 rec(left-1, curr+1)第二个选项是创建一个高度应大于 curr 的新台阶，即 rec(left-curr-1, curr+1) (您创建了一个高度为 curr+1 的台阶)。现在，left永远不能为负，因此 if left<0 then return 0 .而当left是 0 这意味着，我们已经创建了一个有效的楼梯，因此 if left==0 then return 1 .

本案例:if dp[left][curr] !=-1只是为了内存。

现在，rec( 212-1, 1 )表示创建了一个高度为 1 的步骤，它是当前步骤。最后的答案1被减去是因为任何有效的楼梯都应该包含至少 2 个台阶，因此，单步楼梯减去 1。

# your code goes here
dp = [ [-1]*501 for i in range(501) ]

def rec(left, curr):
    if left<0:
        return 0
    if left==0:
        return 1
    if dp[left][curr] !=-1:
        return dp[left][curr]
    dp[left][curr] = rec(left-1, curr+1) + rec( left-curr-1, curr+1)
    return dp[left][curr]

print ( rec(212-1,1) - 1 )

如果您无法理解代码，请随时发表评论。