推 LPH66: top-down 是遞迴, bottom-up 才叫 DP 09/10 01:19
→ LPH66: 然後 top-down 加記錄的叫做筆記法 (memoization) 09/10 01:19
這是我從 Wiki 的頁面上找來的
通常許多子問題非常相似，為此動態規劃法試圖僅僅解決每個子問題一次，
從而減少計算量：一旦某個給定子問題的解已經算出，則將其記憶化（en:memoization）
存儲，以便下次需要同一個子問題解之時直接查表。
這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。
top-down 的,有用到記憶搜索,應該也可以算 DP 吧?
→ LPH66: 這題要 bottom-up 當然也行, 從 k = 0 開始 09/10 01:20
→ LPH66: 每個 k 枚舉所有乘號位置去計算 09/10 01:20
推 suhorng: 不過一樓這種分法碰到有 lazy data structure 的語言就 09/10 01:45
→ suhorng: 很難分清楚了XD 09/10 01:45
→ pttworld: 剪枝條件是什麼，全跑完做法討論串原po已經講了。 09/10 03:17
推 FRAXIS: 只要用 memoization 就好了 應該不太需要剪枝吧 09/10 08:05
對啊,有把結果記下來應該就不需要剪枝了吧?
全跑完的作法不是算排列組合嗎?這個作法不是暴力搜尋
推 suhorng: 有 memoization 就已經不是全跑完了吧 09/10 08:44
→ pttworld: 請問記憶之前參考條件為何。這一格參考上一層該格的條件 09/10 12:58
※ 編輯: dibery (111.184.18.6), 09/10/2016 17:47:05
推 LPH66: >suhorng 所以 DP 本質還是遞迴啊, 只是計算順序的差別而已 09/11 03:31
→ LPH66: lazy eval 就是能夠讓 top-down 定義的東西能 bottom-up 求 09/11 03:31
→ LPH66: 而 DP 只是我們自己去整理到底 bottom-up 一共要哪些東西 09/11 03:32
→ LPH66: 一口氣算完之後堆疊上來而已 09/11 03:32
推 suhorng: 基本上條件就是這個 max_product 的兩個參數. 由於每一次 09/13 10:52
→ suhorng: 插入乘號兩邊都會變小, 所以 max_product 不會循環參考 09/13 10:52
→ suhorng: 本格 max_product 就是 max prefix*max_p..(suffix,num) 09/13 10:53