如何獲得遞歸調用中的路徑

一個孩子正在用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

如何獲得遞歸調用中的路徑

回答

相關問題