在一个由n个数字组成的数字串中插入r个乘号（1 <= r < n），将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的
乘积最大。
例如，对给定的数串267315682902764如何插入6个乘号，使其乘积最大？
插入r个乘号是一个多阶段决策问题，应用动态规划来求解。
使用动态规划需要找到状态递推关系，阶段自然就是插入的乘号了。
设 f(i, k)表示在前i位数中插入k个乘号所得乘积的最大值，a(i, j)表示从第i位到第j位组成的整数值，先看一个实例：
对给定的的9个数字的数串84731926，如何插入5个乘号，使其乘积最大？
目标是f(9, 5)。
设前8个数字中已插入4个乘号，则最大乘积为f（8，4）* 6
设前7个数字中已插入4个乘号，则最大乘积为f（7，4）* 26
设前6个数字中已插入4个乘号，则最大乘积为f（6，4）* 926
设前5个数字中已插入4个乘号，则最大乘积为f（5，4）* 1926
一般为了求取f(i，k)，考察数字串的前i个数字，设在前j （k<= j < i）个数字中已插入k-1个乘号的基础上，在第j个数字后插入第k个乘号，此时的最大乘积为f（j, k-1）* a(j+1,i)。
由此可得递推关系式：
f(i, k) = Max( f(j, k - 1) * a(j+1, i) ));
边界就是当k=0的时候，即插入0个乘号。在递推的过程中，可以使用额外的c[i][j]数组来记录乘号插入的位置。
这道题难度中等，思路不容易想到，此外就是编码的时候容易出错，需要多多练习。
下面是本题的c代码实现：
* n个数插入r个乘号使得乘积最大
* f[i][j] 表示前i个数中插入j个乘号的最大值。
* f[i][j] = MAX(f[i-k][j-1]*a[i-k+1 ~ i])
#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
void main()
double f[30][20] = {0}, d;
int a[30] = {0}, i, j, k, m, n, r, c[30][20] = {0}, b[20];
char l[30];
printf("输入数列："); scanf("%s",l);
printf("输入插入乘号的个数："); scanf("%d", &r);
n = 0;
while(l[n] != '\0'){
//字符转换成数字
a[n] = l[n] - 48;
//边界初始化
for (i = 0; i < n - r; i++)
for (d = 0, j = 0; j <= i; j++)
d = d * 10 + a[j];
f[i][0] = d;
for (j = 1; j <= r; j++)
for (i = j; i < n - r + j; i++)
for (k = j; k < i; k++)
for (d = 0, m = k + 1; m <= i; m++)
d = d * 10 + a[m];
if (f[i][j] < f[k][j-1] * d)
f[i][j] = f[k][j-1] * d;
//保存乘号的位置
c[i][j] = k;
//打印最优解
b[r] = c[n-1][r];
for(j = r - 1; j > 0; j--)
b[j] = c[b[j+1]][j];
for (j = 1, i = 0; j <= r; j++)
while (i <= b[j])
printf("%c", l[i++]);
printf(" * ");
printf(" = %0.1f\n", f[n-1][r]);
参考资料：
1. 数据结构 : C语言版/ 严蔚敏，吴伟民编著
=============================================================================================
Linux应用程序、内核、驱动开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。
先看题目：在一个由n个数字组成的数字串中插入r个乘号（1 <= r < n），将它分成r+1个整数，找出一种乘号的插入方法，使得这r+1个整数的乘积最大。例如，对给定的数串267315682902764如何插入6个乘号，使其乘积最大？插入r个乘号是一个多阶段决策问题，应用动态规划来求解。使用动态规划需要找到状态递推关系，阶段自然就是插入的乘号了。设 f(i, k)...
给定一个非负整数，用k个
乘号
将其分割，使得
乘积
最大
。
例如：在整数12345
中
插入
两个
乘号
，有以下
插入
法：1*2*345 1*23*45 1*234*512*3*45 12*34*5123*4*5
其
中
最大
值是123*4*5 = 2460
一行两个非负整数，非负整数s（0 <= s <= 10^10）和
乘号
的个数k（0 <= k < s的位数）
一行一个整数，即
乘积
的
最大
值
12345 2
例子输...
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动
中
，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为 N 的数字串，要求选手使用 K 个
乘号
将它分成 K+1 个部分，找出一种分法，使得这K+1 个部分的
乘积
能够为
最大
。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312，
最大
K
乘积
问题
问题
描述
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k个整数的
乘积
称为I的一个k
乘积
。试设计一个算法，对于给定的I和k，求出I的
最大
k
乘积
。
例如十进制整数 1234 划分为 3 段可有如下情形：
1 × 2 × 34 = 68
1 × 23 × 4 = 92
12 × 3 × 4 = 144
对于给定的I 和k，编程计算I 的
最大
k
乘积
。
数据...
//请在123456789
中
插入
3个
乘号
，使得
乘积
最大
？请问
乘积
最大
是多少？
#include
#include
using namespace std;
long lMax = 0;
int iflag[9]={0,0,
本文主要对
动态规划
算法做以介绍与总结，并利用该算法实现对网格
问题
、杰克租车
问题
以及赌徒
问题
的仿真，其
中
尤其对于赌徒
问题
笔者进行了
几个
拓展思考，但毕竟水平有限，不尽人意之处还望各位海涵斧正。文章的开头推荐两个笔者认为不错的博客供各位参考学习：
Jabes：强化学习基础篇（三）
动态规划
之基础介绍https://www.jianshu.com/p/ac52910f19a1Jabes：强化学习基础篇（二十三）策略迭代之租车
问题
https://www.jianshu.com/p/338b...
问题
描述：
给出 NNN 个 111 - 999 的数字 (v1,v2,…,vN)(v1,v2,…,vN)(v1,v2,…,vN)，不改变它们的相对位置，在
中
间加入 KKK 个
乘号
和 N−K−1N-K-1N−K−1 个加号，括号随便加，使最终结果
最大
。因为
乘号
和加号一共就是 N−1N-1N−1 个，所以恰好每两个相邻数字之间都有一个符号。
例如： N=5N=5N=5, K=2K=2K=2，555 个数字分别为 111、222、333、444、555，可以进行如下运算：
1∗2∗(3+4+5)=241*2*(
一、
乘积
最大
（简单、线性DP）
考虑限制条件：数字串的长度N 和
乘号
个数K。用dp[i][j]来表示字符串
中
前 i 个数，在使用k个
乘号
的情况下的
最大
乘积
。
那么dp[i][0] = 这个字符串构成的数，我们要找的答案=dp[N - 1][K - 1]。
dp[i][j]怎么得到？我们可以对最后一个
乘号
：
考虑最后一个
乘号
，前面还有 j - 1 个
乘号
，这 j - 1 个
乘号
，至少需要 j 个数来乘，所以最后一个
乘号
的枚举位置，应该从 j 开始，枚举到 i -
给出N个1-9的数字 (v1,v2,…,vN), 不改变它们的相对位置, 在
中
间加入K个
乘号
和N-K-1个加号, 括号随便加,
使最终结果
最大
。因为
乘号
和加号一共就是N-1个，所以恰好每两个相邻数字之间都有一个符号。
例如： N=5, K=2，5个数字分别为1、2、3、4、5，可以进行如下运算：
1*2*(3+4+5)=24
1*(2+3)*(4+5)=45
(1*2+3)*(4+5)=45
Input
第一行输入M(M<=10)表示有M组数据。每
Levenshtein距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，
插入
一个字符，删除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫LevenshteinDistance。
字符串A:abcdefg
字符串B:abcdef
通过增加或是删掉字符”g”的方式达到目的。这两种方案都需要一次操作。把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个...
qq_25644493:
IPv6扩展头部 (三) 路由头部 Routing Header for IPv6
qq_25644493:
