# 几个经典的动态规划问题

《便宜的旅行》分析：

F(s[i])=min{f(s[j])}+value[i]; 0<=s[i]-s[j]<=800

《蛙人 蛙人》 蛙人

F(i+ak,j+tk)=min{f(i,j)+Wk}

for i:=0 to 21 do for j:=0 to 79 do a[i,j]:=10000000; a[0,0]:=0; for i:=1 to n do begin readln(b[i,1],b[i,2],b[i,3]); for j:=21-b[i,1] downto 0 do for k:=79-b[i,2] downto 0 do begin if a[j,k]>a[j,k+1] then a[j,k]:=a[j,k+1]; if a[j,k]>a[j+1,k] then a[j,k]:=a[j+1,k]; if a[j+b[i,1],k+b[i,2]]>a[j,k]+b[i,3] then a[j+b[i,1],k+b[i,2]]:=a[j,k]+b[i,3]; end; end; writeln(a[x,y]); close(input);close(output); end.

f[i,j]=max{f[i-1,j-wi]+pi (j>=wi), f[i-1,j]}

13 如图:

7

14

6

f[1,4]=min{f[1,3],f[1,2]+f[3,4],f[2,4]}+40; f[1,3]=min{f[1,2],f[2,3]}+34; f[1,2]=20; f[2,3]=21; f[3,4]=20; f[2,4]=min{f[2,3],f[3,4]}+27; 引入记号:g[i,j]表示从 i 到 j 堆沙子的重量之和。 一般的： f[1,n]=min{f[1,n-1],f[1,2]+f[3,n],f[1,3]+f[4,n],...,f[2,n]}+g[1,n]

F[i,j]=min{f[i,k]+f[k+1,j]}+W[i,j] (1<=i<=k<=j) F[i,i]=0

i,j,k:integer; n,min:integer; begin assign(input,'stone.txt'); reset(input); readln(n); for i:=1 to n do read(s[i]); close(input); fillchar(g,sizeof(g),0); fillchar(f,sizeof(f),0); for i:=1 to n do for j:=i to n do g[i,j]:=g[i,j-1]+s[j]; for i:=2 to n do for j:=1 to n-i+1 do begin min:=30000; for k:=j to j+i-2 do if min>f[j,k]+f[k+1,j+i-1] then min:=f[j,k]+f[k+1,j+i-1]; f[j,j+i-1]:=min+g[j,j+i-1]; end; writeln(f[1,n]); end.

F(i)=max{F(j)+1}(j<I , bj<bi)

inc(n); read(f,b[n]) end; close(f) end; Procedure main; var i,j,t :integer; order :array[1..maxN]of integer; total :array[1..maxN]of longint; begin f[1]:=1;len:=1; {求解最大不下降序列长度} for i:=2 to n do begin f[i]:=1; for j:=1 to i-1 do if (b[i]>b[j])and(f[i]<f[j]+1) then f[i]:=f[j]+1; if f[i]>len then len:=f[i] {记录最大值} end; for i:=1 to n do order[i]:=i; for i:=1 to n do {排序} for j:=i+1 to n do if (b[i]>b[j])or(b[i]=b[j])and(f[i]>f[j]) then begin t:=b[i];b[i]:=b[j];b[j]:=t; t:=f[i];f[i]:=f[j];f[j]:=t; t:=order[i];order[i]:=order[j];order[j]:=t end; tot:=0; {计算序列个数} fillchar(total,sizeof(total),0); for i:=1 to n do begin if f[i]=1 then total[i]:=1 else for j:=i-1 downto 1 do if (f[j]=f[i]-1)and(b[j]<b[i])and(order[j]<order[i]) then if (b[j+1]<>b[j])or(f[j+1]<>f[j])or(order[j+1]>=order[i]) then inc(total[i],total[j]); if (f[i]=len)and(b[i]<>b[i+1]) then {记录累加最终值} tot:=tot+total[i] end; end; Procedure out; {输出} begin assign(output,fout);rewrite(output); writeln(len); writeln(tot);

close(output) end; Begin init; main; out End.

[问题描述] 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。 确切地 说，若给定序列 X=<x1,x2,……,xm>，则另一序列 Z=<z1,z2,……,zk>是 X 的子序列是指存在 一个严格递增的下标序列 <i1,i2,……,ik>，使得对于所有 j=1,2,……,k 有：

[参考程序] Program p8_2(Input, Output)； const maxlen=200； var i,j:longint； c:array[0..maxlen,0..maxlen] of byte； x,y,z:string； begin assign(input,'lcs.in')； reset(input)； readln(x)； readln(y)； close(input)； fillchar(c,sizeof(c),0)； for i:=1 to length(x) do for j:=1 to length(y) do if x[i]=y[j] then c[i,j]:=c[i-1,j-1]+1 else if c[i-1,j]>c[i,j-1] then c[i,j]:=c[i-1,j] else c[i,j]:=c[i,j-1]； z:=''； i:=length(x)； j:=length(y)； assign(output,'lcs.out')； rewrite(output)； writeln(c[i,j])； while (i>0) and (j>0) do if x[i]=y[j] then begin z:=x[i]+z；i:=i-1；j:=j-1 end else if c[i-1,j]>c[i,j-1]

then i:=i-1 else j:=j-1； if z<>'' then writeln(z)； close(output) end.

2.动态规划问题中的术语 阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段 数就可能不同.描述阶段的变量称为阶段变量。在...

★经典动态规划收集

※动态规划经典教程