※ 引述《cutekid (可愛小孩子)》之銘言：
: 給定一個數字 N (由 1 ~ 9組成)
: 其中插入 K 個乘號，使最後相乘的值要最大
: 舉例:
: N = 746589, K = 2, 最大值 = 7465 x 8 x 9
: N = 1111114, K = 3, 最大值 = 11 x 11 x 11 x 4
: 請問這題除了 C(長度 - 1,K) 暴力搜尋
: 還有什麼比較好的算法嗎
: 謝謝 ^_^
寫一下我的想法,有錯請告知
這裡就先不考慮 overflow 的問題
設計函式 max_product( number, k ) 代表在 number 裡插入 k 個乘號
以你第一個例子
要求解 max_product( 746589, 2 )
它的解是
7 * max_product( 46589, 1 )
74 * max_product( 6589, 1 )
746 * max_product( 589, 1 )
7465 * max_product( 89, 1 )
這其中一個
74658 * max_product( 9, 1 ) 因為 9 沒法插一個乘號進去所以不算
然後每一個結果都可以存下來,遞迴就不用每次跑
算是 top-down 的 DP 吧,複雜度估計大概是 O( nk )
遞迴的終止條件是 k = 0
感覺用 python 會比較好寫XD

top-down 是遞迴, bottom-up 才叫 DP然後 top-down 加記錄的叫做筆記法 (memoization)這題要 bottom-up 當然也行, 從 k = 0 開始每個 k 枚舉所有乘號位置去計算

不過一樓這種分法碰到有 lazy data structure 的語言就很難分清楚了XD

剪枝條件是什麼，全跑完做法討論串原po已經講了。

只要用 memoization 就好了 應該不太需要剪枝吧

有 memoization 就已經不是全跑完了吧

請問記憶之前參考條件為何。這一格參考上一層該格的條件

>suhorng 所以 DP 本質還是遞迴啊, 只是計算順序的差別而已lazy eval 就是能夠讓 top-down 定義的東西能 bottom-up 求而 DP 只是我們自己去整理到底 bottom-up 一共要哪些東西一口氣算完之後堆疊上來而已

基本上條件就是這個 max_product 的兩個參數. 由於每一次插入乘號兩邊都會變小, 所以 max_product 不會循環參考本格 max_product 就是 max prefix*max_p..(suffix,num)