c++ 那边有人问了个题，我不会，在这边求个方法。

设有一个长度为N的数字串，要求使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

f(i, j) 的 j 表示什么？另外每个 f(i, j) 都是个数组是吧？

原来几乎就是穷举。c++ 那边有个人瞎答了个类似分治的算法，搞的我想了半天也没想通。


[ 本帖最后由 pangding 于 2012-6-23 22:25 编辑 ]

是个不错的答案。我等一天，明天结帖。

嗯，我说的不太专业。应该叫动态规划。
当然算过的地方不用再算了，我当时的穷举意思是每每多加一个乘号，就得把所有可能插乘号的地方试遍。能用的性质只有 a*b，当 b 不变的时候，a 越大积越大而已。

我昨天也觉得这个题可能有类似贪心法的算法，但确实有些问题很难处理。

比如 198910 加两个乘号：
1 * 98 * 910 = 89180 < 19 * 8 * 910 = 138320

而且还有类似这样的例子：
999999 加一个乘号答案应该是： 999 * 999；而加两个，却是 99 * 99 * 99。
所以合并分点的位置，也需要从全局考虑。局部最优解可能不能推到整体最优。

[ 本帖最后由 pangding 于 2012-6-24 10:44 编辑 ]