謝謝 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