动态规划算法初步指南.ppt

动态规划算法： * 定义f[i,j]表示从第i到第j堆间合并为一堆的最小代价。 a[i],……,a[j] 共有j-i+1堆石子 sum[i,j]=a[i]+a[i+1]+…+a[j] 状态转移方程：f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j] 枚举位置k：i=k=j-1 初始：f[i,i]=0; ans=f[1,n] 实现方法1：记忆化有哪些信誉好的足球投注网站 * a[i]:记录第i堆石子数量。 s[i]=a[1]+a[2]+…+a[i]。//前缀和 sum[i,j]=s[j]-s[i-1]. readln(n); s[0]:=0; for i:=1 to n do begin read(a[i]); s[i]:=s[i-1]+a[i]; end; 有哪些信誉好的足球投注网站过程： * function dfs(i,j:longint):longint;//合并i..j var k:longint; begin if i=j then exit(0);// 初始f[i,j]:=0; if f[i,j]0 then exit(f[i,j]);//已经求过 f[i,j]:=maxlongint;//为求最小值准备 for k:=i to j-1 do f[i,j]:=min(f[i,j], dfs(i,k)+dfs(k+1,j)+s[j]-s[i-1]); exit(f[i,j]); // dfs=f[i,j] 返回函数值 end; * 0 7 20 36 47 61 0 10 25 34 48 0 11 20 34 0 7 17 0 6 0 3 4 6 5 2 4 1 2 3 4 5 6 1 2 3 4 5 6 f[i,j]:第i到第j堆间合并为一堆的最小代价。 f[i,j]:={f[i,k]+f[k+1,j]}+sum[i,j] * f[2,5]=min(f[2,2]+f[3,5];f[2,3]+f[4,5];f[2,4]+f[5,5])+sum[2,5]=min(20,10+7,25)+17=34 递推法：合并第 i堆 到第 j堆 * for i:=1 to n do f[i,i]:=0;{初始化} for p:=1 to n-1 do //合并的堆数p: 阶段 for i:=1 to n-p do //枚举状态： begin j:=i+p; f[i,j]:=maxlongint; for k:=i to j-1 do {枚举决策} f[i,j]:=min(f[i,j],f[i,k]+f[k+1,j]); f[i,j]:=f[i,j]+s[j]-s[i-1]; end; 时间:O(n3) 总结本题： * 1、前缀和的应用。 2、区间的dp的求解方法： 不能顺推也不能倒推。 是以区间长度的大小划分阶段。 按区间从小到大的顺序划分。 扩展一下：NOI95 * 石子由一排改为围成一个环的形状？ 4 5 9 4 4 5 9 4 4 5 9 环形石子合并算法： * 环变成线性:长度: 2n-1 a[1],a[2]......a[n],a[n+1].....a[2n-1]; a[n+i]=a[i] f[i,j]:合并i到j堆的最小得分。 f[i,j]=min{f[i,k]+f[k+1,j]}+s[j]-s[i-1] . (i=k=j-1) 目标：ans=min{f[1,n],f[2,n+1],...,f[n,2n-1]} time O(n^3)} 例11：括号序列 * 定义一个合法的括号序列： （1）空序列是合法的 （2）假如S是一个合法的序列，则 (S) 和[S]都是合法的 （3）假如A 和 B 都是合法的，那么AB和BA也是合法的 例如以下是合法的括号序列： (), [], (()), ([]), ()[], ()[()] 以下是不合法括号序列的： (, [, ], )(, ([]), ([()，([)] 给定一些由‘(’,‘)’,‘[’, ‘]’构成的序列 ，求最少添加多少个括号，能得到一个合法的括号序列。 * 【输入】 序列s(长度=100). 【输出：】 使序列s成为合法序列添加最少的括号数量。 【样例输入】 ([() 【样例输出】 2 【样例说明】最少好添加2个括号可以得到合法的序列： ()[()]或([()])或([])() 分析： * 设括号序列：SiSi