※ 引述《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)