乘积最大(分不够可以再加！)
问题描述:
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先
生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活
动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样
一道题目:
设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种
分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串: 312，当N=3，K=1时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
输入：
程序的输入共有两行:
第一行共有2个自然数N,K (6 <=N <=40，1 <=K <=6)
第二行是一个K度为N的数字串。
输出:
结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。
样例:
输入
4 2
1231
输出
62
想要完整的源码，分不够可以再加！！
[解决办法]
这不应该复杂吧，用暴力方法的话，大概这么做吧 （假定涉及的乘积都小于int的最大数，否则的话，大概需要自己写大整数类或者使用.NET 3.5里的BigInteger类）：
using System;
class MyPath
{
static int MaxProduct(int mulOpCount, char[] nums, int start, int length)
{
if (length <= mulOpCount)
{
throw new ArgumentException( "乘法算符数目太多了 ");
}
if (mulOpCount == 0) //如果乘法算符数目为0，则返回当前字符数组对应的整数值
return ConvertCharArrayToInt(nums,start,length);
int maxProduct = 0;
for (int i = 0; i < length-mulOpCount;i++)
{
int left = ConvertCharArrayToInt(nums,start,i+1);
int right = MaxProduct(mulOpCount-1,nums,start+i+1, length-i-1);
int p = left*right;
if (p > maxProduct)
maxProduct= p;
}
return maxProduct;
}
static int ConvertCharArrayToInt(char[] nums, int start, int length)
{
string s = new string(nums,start, length);
return Convert.ToInt32(s);
}
static void Main(string[] args)
{
if (args.Length < 2)
{
Console.WriteLine( "{0} number-string multiplication-count ", Environment.GetCommandLineArgs()[0]);
return;
}
char[] numChars = args[0].ToCharArray();
int mulOpCount = Convert.ToInt32(args[1]);
Console.WriteLine( "{0} ", MaxProduct(mulOpCount,numChars,0,numChars.Length));
}
}
[解决办法]
如果用暴力破解，假设N=40,K=6,则总共有39*38*37*36*35*34=2349088560中分法，做这么多次的大整数乘法再比较，恐怖。。。。。。
我的感觉是分出来的所有的数的位数应尽量一样，不一样的话，留大数，拆小数。
不知道想法对不对。
[解决办法]
我仔细想了想，觉得K应该为1是最好的，从中间分开，大家试试看是不.
[解决办法]
所以这个问题有2种情况，例如5位数，99899，是拆成998*99，还是拆成99*899呢，就只对前(n/2)位和后(n/2)位进行判断就可以了,
还有一种情况就是中间0太多的，例如:10001，这种情况，就从最中间的0开始数，如果右边还是0，就继续将*右移，一直移到右边的数不为0。
如果要是100000的话，那怎么算最大值都是0咯。
[解决办法]
确实牛人。
是否可以引入平均值概念
例如 312，N=3,K=1那么(3+1+2)/(K+1)=2,任何小于2的数都不能看分开312里面的1就必须附于其他数上面。
[解决办法]
需要用到排列组合，N长度，那么就有N-1个空用来放*号，从这N-1个空中取出K个空来放*，只能循环比较解决吧
------解决方案--------------------
搞竞赛的人都应该做过这道题（显然是2000年的题嘛）。
题目给出两个关键数值N和K对不对？假设F(N,K)就是对字符串前N位插入K个乘号后所能得到的最大值，考虑一下F(N,K)与F(N-1,K)、F(N-1,K-1)的关系？如果你也是搞竞赛的，点到即止。算法题应该到算法版问，你在ASP.NET版问，大家平常都不是研究这个的，你能得到的答案可能就不是那么优化。
[解决办法]
附例子：
312：当N=3, K=1时，从N=1, K=0开始推导
F(1, 0) = 3
F(2, 0) = 31
F(3, 1) = max(F(1, 0)*12, F(2,0)*2) = max(36, 62) = 62
31245：N=5, K=2，还是从F(1, 0)开始推导
F(1, 0) = 3
F(2, 0) = 31
F(3, 0) = 312
F(2, 1) = 3*1 = 3
F(3, 1) = max(F(1, 0) * 12, F(2, 0) * 2) = max(36, 62) = 62
F(4, 1) = max(F(1, 0) * 124, F(2, 0) * 24, F(3, 0) * 4) = max(372, 744, 1248) = 1248
F(5, 2) = max(F(2, 1) * 245, F(3, 1) * 45, F(4, 1) * 5) = max(735, 2790, 6240) = 6240
因为题目仅需要求最后的值，不需要输出到底是如何插入乘号能得到这个最大值（通常竞赛题都这样），因此这样的计算方法获得最大值就足够了。如果你要追寻哪种插入方式得到了最大值，每次max时你都要把最大值的选择保存下来，最后根据这个选择确定原先进行了乘号插入的地方。
[解决办法]
动态规划
给你规划方程吧：
设A[I，Num] B[I,Num] 是第一个数字到第I个数字中加Num个乘号所得的最大值
s[k，I]表示从第k位到第I位的一个数字
那么
B[I，Num]=max（A[k，Num-1]*S[k+1，I])
1+Num-1 <=k <=I;
不过细心一点还是比较好写的
