記憶和接口

Question

1. 記憶遞歸解決方案是否具有與非遞歸解決方案相同的複雜性？我認爲遞歸解決方案的大部分時間花費更多，但是使用memoization技術，我不明白爲什麼我不應該總是使用遞歸？它更短，更易於理解

2. 接口問題 - 是否可以聲明一個函數，該函數將強制使用接口的人在其中應用部分代碼？或者我只能聲明函數的簽名，就是這樣？由於Android的，例如我可以實現監聽器和方法裏面我看行代碼，我不能改變這比我已經習慣了

Answer 1

正常執行不同的關於動態編程，你有兩種選擇：自上而下的方法（記憶遞歸）和自下而上的方法。自下而上的方法使用循環構建查找數組，因此它比遞歸更高效，這會花費堆棧分配並消耗時間。通過遞歸記憶，您只需「記住」您找到的解決方案，以免重複計算相同的問題。因此，在解決問題之前，先檢查當前問題是否先解決。這是它和回溯之間的區別，它們重複解決相同的問題，因此需要重複的時間。