文档介绍:动态规划
动态规划
什么是动态规划
动态规划的条件
动态规划的关键
几种常见动态规划的种类
例题分析
什么是动态规划
动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题
但是经分解得到的子问题往往不是相互塔问题,于是可以借助动态规划高效解决。
状态的确定
我们用opt[i][j]表示从左上角入口移动到第i行j列的最小代价。
则opt[i,j]=min{opt[i-1][j], opt[i][j-1]) + a[i][j];
最终输出opt[n][n];
代码
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf(“%d”, &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <=n; j++)
f[i][j] = min(f[i-1][j], f[i][j-1]) + a[i][j];
printf(“%d\n”, f[n][n]);
乘积最大
国际数学联盟确定的“2000—世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛活动,你的好挚友XZ也有幸得以参与。活动中,主持人给全部参与活动的选手出了这样一道题目:
设有一个长度为N(N≤40)的数字串,要求选手运用M(M≤6)个乘号将它分成M+1个部分,找出一种分法,使得这M+1个部分的乘积最大。
同时,为了帮助选手能够理解题意,主持人还举了如下一个例子:
有一个数字串:312,当N=3,M=1时会有两种分法:
⑴3×12=36
⑵31×2=62
这时,符合题目要求的结果是:31×2=62。现在,请你帮助你的好挚友XZ设计一个程序,求得正确的答案。
分析
由于自然数位数的上限为40,乘号数的上限为6,因此最大乘积位数的上限接近42位。明显,运算任何整数类型都无法容纳如此之大的数据,只能接受高精度运算,限于篇幅,对于高精度的加法运算、乘法运算和比较大小的运算,这里不作介绍,只是对的乘号最佳插入方式进行探讨:
假设s1‥si(2≤i≤n)中插入j个乘号,其中s1‥sk中插入了j-1个乘号,即乘式中的第j+1项为sk+1‥si(j≤k≤i-1):
分析
设
ans[i][j]——长度为i的数串中插入j个乘号的最大乘积(整型数组)。明显
ans[i][0]=s1..si对应的整型数组;
ans[i][j]=max{ans[k][j-1]×sk+1..si} (1≤i≤n, 1≤j≤min{i-1,m},j≤k≤i-1)
ans[n][m]即为其解。
分析
由于乘式中第j+1项sk+1‥si为常量,因此要使得ans[i][j]最大,则s1‥sk中插入j-1个乘号的乘积必需最大;同样,为了找寻第j个乘号的最佳插入位置,必需一一查阅子问题ans[j][j-1]‥ans[i-1][j-1]的解。明显该问题具备无后效性、最优子结构的特征,适用于动态规划方法。
状态的确定
我们用ans[i][j]表示前i个字符插入j个乘号可以获得的最大值
则有:
ans[i][0]=s1..si
ans[i][j] = max{ans[k][j-1]×sk+1..si} (j≤k≤i-1)
ans[n][m]即为其解。
代码
输入n,m和数串s;
for i←1 to n do ans[i][0]←s1..si对应的整数数组;
for i←2 to n do
{阶段:枚举数串的长度}
for j←1 to min{i-1,m} do
{状态:枚举长度为i的数串中插入的乘号个数}
for k←j to i-1 do
{决策:枚举第j个乘号的插入位置}
begin
next←sk+1..si对应的整数数组; {计算第j+1项}
ans[i][j]←max{ans[i][j], ans[k][j-1]×next};
{计算状态转移方程}
end;{for}
输出最大乘积ans[n][m];
过河
在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很厌烦踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点起先,不停的向终点方向跳动。一次跳动的距离是S到T之间的