保存結果的最佳方式 - 動態編程

我正在努力解決一個類似於Euler Problem 215的問題。我想我可以在不解釋整個問題和/或解決問題的完整方法的情況下解釋這一點。保存結果的最佳方式 - 動態編程

現在我正在用RT（數組的Arraylist，int i）進行遞歸調用。根據這項技術，我想保存結果，所以如果當RT要求相同的問題時，我可以簡單地查找答案，而不是重複，直到達到基本情況。只是爲了說明RT（[3,7.5,10.5,15]，2）。在遞歸中，右側的權利遞增。 Arraylist用於確定需要回憶的基本情況。

在美國，我對動態規劃的理解通常使用二維數組，其中結果被保存並使用被稱爲參考點的地方進行存儲。如果它像RT（int x，int y）那麼這很棒。但是我的問題呢？

我想我可以更改ArrayList字符串37510515，然後到一些使用的ASCII碼或數字本身。但我希望我可以像HashMap那樣使用ArrayList作爲鍵，但是這個HashMap中的缺陷只適用於一個值（我知道我可以鏈接，但是如何在存儲結果的同時工作很容易跟蹤什麼「INT我」它被稱爲？）

因此，總之，任何人都可以幫助我想到一種方法來存儲與ArrayList和int作爲兩個引用的結果？

在此先感謝！

來源

2012-01-19 user1159243

是數組總是按照相同的順序？那很重要嗎？如果不是的話，那麼一棵B樹就可以工作，並且會保持最小讀數。如果你幸運的話，你可以做1次查找。最壞的情況下，你必須通過（在你的情況下）樹的5個層次。 – jasonmclose

你可以用你喜歡的，作爲一個HashMap密鑰的任何類的對象，它會工作，如果對象定義equals（）和hashCode（）方法正確。這些方法已經在ArrayList中正確實現，因此您應該發現使用ArrayLists作爲HashMap鍵非常合適。

如果你想使用一個ArrayList和一個數字組合作爲HashMap的關鍵字，你可以爲此定義一個類，在該類中實現hashCode（）和equals（），或者通過使編號僅僅是數組列表中的最後一個條目。

這聽起來像你正在做的是比動態編程更像http://en.wikipedia.org/wiki/Memoization，但它可能會完成工作 - 我想歐拉問題已被設置爲使其適用於最好的技術 - 如果這是記憶或動態編程你應該覺得它是實惠的。這需要太長的時間，然後我們都錯過了一些更有效的方法。

進一步加速的一種方法是利用問題的對稱性 - 例如，如果您的狀態與塊的行（或列）相對應，那麼這與基本相同的狀態與從右向左而不是從左向右或從下向上而不是從上向下佈置的相同塊的行相同。

來源

2012-01-19 19:57:54 mcdowella

謝謝。我接受了你的建議。我採取了簡單的方法，只是將數字添加到ArrayList，而不是創建一個新對象並定義它的equals（）和hashCode（）。我將它稱爲一個小的「黑客」，因爲我以一種無意的方式使用它。但是，現在它仍然有效。 – user1159243

要解決的一個方法是實現自己的類包裝arraylist & int，寫hashCode和equals如上所述。

Using a byte array as Map key

來源

2012-01-19 19:50:15

保存結果的最佳方式 - 動態編程

回答

相關問題