谢谢 dibery
我将你的想法理解后实作了一遍
程式网址(Perl): http://codepad.org/cicXQTmo
用了 bottom-up 迭代的方式计算 max_product (舍去递回)
时间复杂度应该是 O( 长度 * 长度 * K )
大于你原来所说的 O( 长度 * K )
以下为原始码:
=============
#!C:\Perl\bin\perl -w
##############
# 欲计算的数字
$N = 746589;
##############
# 插入几个乘号
$K = 2;
##########
# 数字长度
$L = length($N);
################
# 产生所有子数字
&GenSubNum;
########################################
# 计算 maxProduct[长度][$k = 0,1,2,3...]
#
# 长度 : left substring length
# k : 插入乘号个数
##########################
# init maxProduct[长度][0]
for($i = 0; $i < $L; ++$i){
$maxProduct[$i + 1][0] = $subNum[0][$i + 1];
}
###############################################
# 迭代 $k = 1,2,3 ... 算出 maxProduct[长度][$k]
for($k = 1; $k <= $K; ++$k){
for($leftLen = $k + 1; $leftLen <= $L - $K + $k; ++$leftLen){
for($i = $k, $max = 0; $i < $leftLen; ++$i){
$v = $maxProduct[$i][$k - 1] * $subNum[$i][$leftLen - $i];
$max = $v if($v > $max);
}
$maxProduct[$leftLen][$k] = $max;
}
}
##############
# print answer
print $maxProduct[$L][$K];
sub GenSubNum {
@digit = split('',$N);
for($i = 0; $i < $L; ++$i){
for($j = $i, $acc = 0, $len = 1; $j < $L; ++$j, ++$len){
$acc = $acc * 10 + $digit[$j];
$subNum[$i][$len] = $acc;
}
}
}
※ 引述《dibery (简哥)》之铭言：
: ※ 引述《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