最大k乘问题
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。设计一个算法，对于给定的I和k，求出I 的最大k乘积。
一、思路：
1）我们定义dp[i][j]为数字I的前i为分成j段时的最大j乘积，如数字123，则dp[1][1]=1，dp[2][1]=12，dp[3][1]=123，dp[2][2]=2，如此类推。
2）那么我们来推导dp[i][j]与dp[i-x][j-1]，其中x<i，假设我们已经知道所有m<i，n<j取值时的dp[m][n]，构成dp[i][j]的可能为dp[i-1][j-1]*num[1..i]，dp[i-2][j-1]*num[2..i]，dp[i-3][j-1]*num[3..i]，dp[i-4][j-1]*num[4..i]……
所以我们把数字num[123…x….i]分为两部分，其中第一部分为num[123…i-x]，第一部分的最大乘积为dp[i-x][j-1]，第二部分为num[x..i]，则dp[i][j]=max(dp[i-x][j-1]* num[x..i])。
3）经过上述分析，我们可以把求I的最大k乘积划分为若干个子问题，这些子问题均为求最大乘积问题，然后通过这些最大乘积计算出I的最大k乘积，满足动态规划的最有自结构和无后向性性质。
4）已知数字I的位数为n，通过上述分析，求取dp[i][j]需要遍历O（n），计算dp[1][1]到dp[n][k]需要遍历O（n*k）的时间复杂度，总共需要O（n*n*k）的时间复杂度。
下列测试通过暴力搜索进行比较，验证了算法的正确性：
| 1234567890 | 最优分解 | 最大k乘积 |
| k=1 | 1234567890 | 1234567890 |
| k=2 | 12345678 90 | 1111111020 |
| k=3 | 1234567 8 90 | 888888240 |
| k=4 | 123456 7 8 90 | 622218240 |
| k=5 | 12345 6 7 8 90 | 373312800 |
| k=6 | 1234 5 6 7 8 90 | 186580800 |
| k=7 | 123 4 5 6 7 8 90 | 74390400 |
| k=8 | 12 3 4 5 6 7 8 90 | 21772800 |
| k=9 | 1 2 3 4 5 6 7 8 90 | 3628800 |
| k=10 | 1 2 3 4 5 6 7 8 9 0 | 0 |
二、复杂度分析
根据上述算法，时间复杂度为O（n*n*k），空间复杂度为O（n*k）。
三、源代码：
[c language=”++”]
//#include<string>
//#include <iomanip>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
#include<vector>
#include <algorithm>
using namespace std;
/*
函数名 ：str2long
函数功能：把str转化long long
*/
long long str2long(string str)
{
long long result = 0;
for (int i = 0; i < str.size(); i++)
{//逐位转化
result = result * 10 + str[i] – ‘0’;
}
return result;
}
/*
函数名 ：devideNumber
函数功能：求出str的最大k乘积
*/
long long devideNumber(string I, int k, vector<vector<int>>&trace)
{
//n表示I的位数
int n = I.size();
//dp[i][j]表示把I前i位分成j段时的最大乘积
vector<vector<long long>> dp(I.size()+1, vector<long long>(k+1));
//初始化分成1段的时候
for ( int i = 1; i <=n; i++)
dp[i][1] = str2long(I.substr(0,i));
//求解dp[i][j]，其中j<=i，i位数字最多划分为i段，所以j不超过i
for (int i = 2; i <=n; i++)
{
for (int j = 2; j <=k && j<=i; j++)
{
long max=0;
for (int m = 1; m < i; m++)
{//把前i位分为两部分，一部分是0~m-1，另外一部分是m~i
int tmp = dp[m][j – 1] * str2long(I.substr(m, i-m));
if (tmp >=max)
{
max = tmp;
//trace的意义是dp[i][j]取得最大值时，最后一个数字为m~i-1
trace[i][j] = m;
}
}
dp[i][j] = max;
}
}
return dp[I.size()][k];
}
int main(void)
{
cout << "|—————————————————————————|\n";
cout << "| 算法实现题7 |\n";
cout << "| |\n";
cout << "| 设 I 是一个n位十进制整数，如果把I划分为k段，则可得到k个整数。 |\n";
cout << "| 这k个整数的乘积称为I的一个k乘积。给定I和k，求出I的最大k乘积。 |\n";
cout << "| |\n";
cout << "|—————————————————————————|\n";
while (1)
{
string I;
int k;
cout << "请输入I的值(输入负数退出)：" << endl;
cin >> I;
if (I[0] == ‘-‘) break;
cout << "请输入划分的段数k：" << endl;
cin >> k;
//异常检测
if (I.size() < k)
{
cout << "输入不合要求！k不能超过I的位数！"<<endl<<
"您输入的I的位数为" << I.size() << "，k的值为" << k << "，请重新输入。" << endl << endl;
continue;
}
else if (k < 1)
{
cout << "k的取值至少为1！请重新输入！" << endl;
}
//trace记录I求出最大k乘积后，每个位置所取的位数
vector<vector<int>> trace(I.size()+1,vector<int>(k+1));
int result=devideNumber(I, k, trace);
cout << "最大k乘积为：" << endl << result << endl;
//回溯分成的段
stack<string> sta;
int tmp = I.size();
for (int i = 0; i < k; i++)
{//通过trace把分成的段记录下来
sta.push(I.substr(trace[tmp][k – i], tmp – trace[tmp][k – i]));
tmp = trace[tmp][k – i];
}
cout << "分成的各段为：" << endl;
while (!sta.empty())
{
cout << sta.top() << " ";
sta.pop();
}
cout << endl<<endl;
}
return 0;
}
[/c]