https://www.jianshu.com/p/98b025c50a46
其中
设I是一个n位十进制整数。如果将I分割为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。
测试:
输入: 2 1 (2是位数,1是分几段)
15 (15是I)
输出:15
输入: 5 2
12345
输出:6170
https://www.dreamxu.com/books/dsa/dp/max-k-product.html测试:
输入: 2 1 (2是位数,1是分几段)
15 (15是I)
输出:15
输入: 5 2
12345
输出:6170
分析:
1、数组m[i][j]为 将前i位数分成j段的最大乘积
2、数组打底:前1位数,分成1段;前2位数,分成1段;前3位数,分成1段......前n位数,分成1段。(就是先计算出前i位的大小)
3、m[i][j]=Max{m[k][j-1]*a[i-k]},其意思就是把前k(1<=k<i)个数分成j-1段,再乘以a[i-k],a[i-k]代表着,第k位到第i位数的数值.......
将一个整数划分位 k 个整数,能不能将其转换为划分成 k-1 个整数的问题呢? 如果可行,同理 k-1 个整数可划分为 k-2 个整数,直到剩下一个整数, 然后将这些划分组合起来,原问题就能求解出来了
事实上确实是可行的,可以这么想:
无论怎么划分,整数 i 的最后 1 位或者多位肯定被划分为一个整数(假设为 l 位), 那么除了这个整数,前面的 n-l 位必定被划分为 k-1 个整数。 假设将 i 划分成 k 个整数,最后一个整数为 l 位,这种情况为最大划分, 那么 i 前面的 n-l 位分成 k-1 个整数必定也为最大划分
无论怎么划分,整数 i 的最后 1 位或者多位肯定被划分为一个整数(假设为 l 位), 那么除了这个整数,前面的 n-l 位必定被划分为 k-1 个整数。 假设将 i 划分成 k 个整数,最后一个整数为 l 位,这种情况为最大划分, 那么 i 前面的 n-l 位分成 k-1 个整数必定也为最大划分
可用反证法证明:
设
设
那么
假设将 i 划分成 k 个整数,最后一个整数为 l 位,这种情况为最大划分, 那么有如下等式成立:
设
mkp[x][y]
表示 i 的前 x 位组成的数分成 y 个整数,这 y 个整数的最大乘积设
num[a][b]
表示取 i 的第 a 到 b 位(包括 a, b 位且第一位为 num[1][1]
)那么
mkp[n][k]
就表示 i 共有 n 位,且将其分成 k 个整数的,这 k 个整数的最大乘积假设将 i 划分成 k 个整数,最后一个整数为 l 位,这种情况为最大划分, 那么有如下等式成立:
mkp[n][k] = mkp[n-l][k-1] * num[l][n]
如果
mkp[n-l][k-1]
不是最大划分,那么必定有 mkp[n-l][k-1]'
为最大划分,即有mkp[n-l][k-1] < 'mkp[n-l][k-1]
那么
mkp[n][k]' = mkp[n-l][k-1]' * num[l][n]
因为
mkp[n-l][k-1]' > mkp[n-l][k-1]
所以
mkp[n][k]' > mkp[n][k]
即
mkp[n][k]
不是最大划分,与上文 mkp[n][k]
为最大划分矛盾
以上证明了: 如果将 i 划分成 k 个整数,最后一个整数为 l 位,这种情况为最大划分, 那么 i 前面的 n-l 位分成 k-1 个整数必定也为最大划分
经过以上分析,我们能够得到如下结论:
mkp[x][y] = mkp[z][y-1] * num[z+1][x]
那么问题来了:我们不知道 z 的值,该怎么得到呢?
对于这个问题规模比较小的情况下,我们可以采用枚举法:
将 z 的所有可能值都取一遍,看看哪个 z 能使
对于这个问题规模比较小的情况下,我们可以采用枚举法:
将 z 的所有可能值都取一遍,看看哪个 z 能使
mkp[z][y-1] * num[z+1][x]
最大, 这个最大值就是 mkp[x][y]
将以上所有思路整理一下,可得到如下最后的结论:
mkp[x][y]
表示 i 的前 x 位组成的数分成 y 个整数,这 y 个整数的最大乘积num[a][b]
表示取 i 的第 a 到 b 位(包括 a, b 位且第一位为 num[1][1]
)mkp[x][y] = x
, 当 y = 1
时,此时只分成一个整数,就是 xmkp[x][y] = max{ mkp[z][y-1] * num[z+1][x] }
, 其中 y-1 <= z < x
, 当 y != 1
时其中
x >= y
是肯定的,因为不可能把一个 n 位的整数分成 n+1 个整数(举个例子), 所以很好理解 y-1 <= z < x
代码
来举个具体的例子实践下吧,要不然都不明白我在说啥
方法和编辑距离是一样的,先把子问题求解出来,然后一步步求解原问题
比如:将 12345 分成 3 个整数
方法和编辑距离是一样的,先把子问题求解出来,然后一步步求解原问题
比如:将 12345 分成 3 个整数
首先定义一个 mkp 矩阵,然后填入 y = 1 时候的值,如下图:
其中打叉叉的是不可能取到的值,y 不可能大于 x
然后是计算
...
计算
y = 2
的时候: 先计算 mkp[2][2]
, 即计算 max{ mkp[z][1] * num[z+1][2] }
, 其中 1 <= z < 2
...
计算
mkp[5][2]
, 即计算 max{ mkp[z][1] * num[z+1][2] }
, 其中 1 <= z < 5
最后计算
y = 3
的时候,直到计算完 mkp[5][3]
, 即可得到原问题的解
填写好的矩阵如下:
int num(int i, int n, int a, int b)
{
return i / (int)pow(10, (n-b)) % (int)pow(10, b-a+1);
}
int max_of_mkpz(int n, int k, int mkp[n+1][k+1], int i, int x, int y)
{
int max = mkp[y-1][y-1] * num(i, n, y, x);
for (int z = y; z < x; z++) {
if (max < (mkp[z][y-1] * num(i, n, z+1, x))) {
max = mkp[z][y-1] * num(i, n, z+1, x);
}
}
return max;
}
int max_k_product(int i, int k)
{
int x, y;
int n = (int)log10(i) + 1;
int mkp[n+1][k+1];
for (x = 1; x <= n; x++) {
mkp[x][1] = num(i, n, 1, x);
}
for (y = 2; y <= k; y++) {
for (x = y; x <= n; x++) {
mkp[x][y] = max_of_mkpz(n, k, mkp, i, x, y);
}
}
return mkp[n][k];
}