如何获得递归调用中的路径

一个孩子正在用n个步骤跑上楼梯，并且可以一次走1步，2步或3步。现在编写一个程序来计算孩子能够爬楼梯的方式。如何获得递归调用中的路径

的解决方案看起来像这样（DP可以用来节省时间）

public static int countDP(int n) { 
if (n<0) 
    return 0; 
else if (n==0) 
    return 1; 
else { 
    map[n] = countDP(n-1) + countDP(n-2) + countDP(n-3); 
return map[n]; } 
}

现在的问题是如何让这些路径？例如对于n = 4，这个函数返回7，如何获得所有可能的路径？（在这个例子中是1111 - 121 - 112 - 211 - 31 - 13 - 22）有没有办法通过改变当前的程序来做到这一点？

这是不是一个家庭作业的问题，它是由递归和开裂编码访书的动态规划章未来 - 第9章 - 问题1.

来源

2013-10-27 user2925218

这看起来像一个功课疑问... – IMSoP

你到目前为止尝试了什么？ –

@IMSoP，如果他们看起来像一个家庭问题复制/粘贴到这里，我们应该还是不应该回答这样的问题？ – Roman

是有办法找到所有的路径，可以落实到您现有的代码。首先，这将是非常昂贵的，空间明智的。即使对于n = 4，您也需要创建7个路径。

我认为，最好的方法是创建一个三元树并分配每个可能的路径可以去每个子节点的方式。所以，这里是一个简单的伪代码：

root.value = 0; 
root.left.value = 1; 
root.middle.value = 2 
root.right.value = 3;

然后，当你做递归，你会每个孩子传递到相应的递归调用。

你需要照顾一些角落案件。另外，考虑你正在使用递归，想想你应该在哪里定义这个三元树。

注：我不想发布实际的代码或给出完整的答案，因为几个人（包括我自己）认为这可能是一个家庭作业问题。正因为如此，我试图帮助解决这个问题，并引导人们找到解决方案，而无需将其交付出去。

来源

2013-10-27 15:33:54 Roman

当您进行递归调用时，您已经创建了一棵树，创建另一棵树并不是最佳答案。我正在寻找一种使用递归树来获取所有路径的方法。这不是一个家庭作业问题，它来自Cracking Coding Interview书的递归和动态编程章节 - 第9章 - 问题1。 – user2925218

@ user2925218查找所有路径，您可以执行DFS的一个版本，该版本将经过树中所有可能的组合。一旦你点击一个叶节点 - 打印（或存储某处）从根节点到叶节点的完整路径。这可以给你一个所有路径的列表。链接到DFS（以防万一）：http://en.wikipedia.org/wiki/Depth-first_search – Roman

上面代码中的遍历就像DFS，递归的基本条件是树叶（当n = 0或n <0），我尝试在叶节点创建相关的字符串，但它不起作用，我正在寻找一种方法来在此代码中插入正确打印路径的语句，但我无法做到。如果我不清楚，请告诉我。 – user2925218

如何获得递归调用中的路径

回答

相关问题