algorithm - 单跳最多回溯n个楼梯n步

你需要爬一个有N级台阶的楼梯，你决定跳上台阶来获得一些额外的锻炼。一次跳最多能跳k步。返回所有可能的跳跃序列，你可以采取爬楼梯，排序。
我的实现显然给了我错误的答案。

def climbingStaircase(n, k):
    final_res=[]
    final_res.append(CSR(n,k,[]))
    return final_res

def CSR(n,k,res):
    if n == 0:
        return res
    else:
        for i in range(1,k+1):
            if n-i>=0:
                res.append(i)
                n=n-i
                res=CSR(n,i,res)
        return res

对于n=4和k=2，输出应该是

[[1, 1, 1, 1],
 [1, 1, 2],
 [1, 2, 1],
 [2, 1, 1],
 [2, 2]]

实际产量：

[[1,1,1,1,2,1]]

有人能指出我遗漏了哪一部分吗？

最佳答案

一个巨大的问题是在下面的代码中：您为步骤范围内的每个可能性扣除步骤的数量。

n=n-i
res=CSR(n,i,res)

当你完成了一步跳转的探索后，你需要从相同的起点（这个实例的初始值n）开始两步跳转。将代码更改为：

res = CSR(n-i, i, res)

这将在循环过程中保持n值不变。
另外，你不能把未来的跳跃限制在你刚拿的最大值也要更改第二个参数：

res = CSR(n-i, k, res)

那会让你动起来的也可以尝试这个可爱的debug博客寻求帮助。至少插入一个或两个跟踪语句，例如

print n, k, res

在你日常生活的顶端。
警告
这不是你所有的麻烦剩下的最大问题是CSR只返回一个解决方案：您执行的每个步骤都附加到同一个列表中。您需要一种方法将已完成的解决方案收集为单独的列表；append中的climbingStaircase只在CSR完全完成后执行一次。
您需要在n==0中识别一个完整的解决方案。
调试帮助
这是您的程序的一个版本，它修复了递归参数，并插入了调试跟踪。

indent = ""

def climbingStaircase(n, k):
    final_res = []
    final_res.append(CSR(n, k, []))
    return final_res

def CSR(n, k, res):
    global indent
    indent += "  "
    print indent, n, k, res
    if n == 0:
        print "SOLUTION", res
    else:
        for i in range(1, k+1):
            if n-i >= 0:
                CSR(n-i, k, res + [i])
    indent = indent[:-2]

print climbingStaircase(4, 2)

注意使用“indent”帮助可视化递归和回溯这里的关键部分是，我没有全局更新res，而是将其作为局部变量。我现在还删除了返回值，只需转储以输出找到的解决方案。你可以看到它是如何工作的：

   4 2 []
     3 2 [1]
       2 2 [1, 1]
         1 2 [1, 1, 1]
           0 2 [1, 1, 1, 1]
SOLUTION [1, 1, 1, 1]
         0 2 [1, 1, 2]
SOLUTION [1, 1, 2]
       1 2 [1, 2]
         0 2 [1, 2, 1]
SOLUTION [1, 2, 1]
     2 2 [2]
       1 2 [2, 1]
         0 2 [2, 1, 1]
SOLUTION [2, 1, 1]
       0 2 [2, 2]
SOLUTION [2, 2]
[None]

有了这些东西，我希望你能追踪你的逻辑，找出如何在你选择的层次上捕捉解决方案的序列。