動(dòng)態(tài)規(guī)劃習(xí)題課件

課程安排

12345678910111213141516周二PPTTPTTPTTPTTTTP周四PPPPPPPPPPPPPP端午考試

T1課程安排12345678910111213141516周二第3章動(dòng)態(tài)規(guī)劃習(xí)題課第3章動(dòng)態(tài)規(guī)劃習(xí)題課最長(zhǎng)單調(diào)遞增子序列(習(xí)題3-1)設(shè)計(jì)一個(gè)O(n2)時(shí)間的算法,找出由n個(gè)數(shù)組成的序列的最長(zhǎng)單調(diào)遞增子序列。輸入第1個(gè)整數(shù)n(0<n<100),表示后面有n個(gè)數(shù)據(jù)，全部為整數(shù)輸出輸出最長(zhǎng)單調(diào)遞增子序列的長(zhǎng)度；樣例輸入865158170155239300207389樣例輸出63最長(zhǎng)單調(diào)遞增子序列(習(xí)題3-1)設(shè)計(jì)一個(gè)O(n2)時(shí)間的算法最長(zhǎng)單調(diào)遞增子序列用數(shù)組b[0:n-1]記錄以a[i](0≤i<n)為結(jié)尾元素的最長(zhǎng)遞增子序列的長(zhǎng)度。序列a的最長(zhǎng)遞增子序列的長(zhǎng)度為：max{b[i]}顯然，b[i]滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，可以遞歸的定義為：b[0]=1;b[i]=max{b[k]}+1即k在0~(i-1)范圍內(nèi),若a[k]≤a[i],尋找最大的b[k].據(jù)此將計(jì)算b[i]轉(zhuǎn)化為i個(gè)規(guī)模更小的子問題。0≤i<n0≤k<ia[k]≤a[i]6515817015523930020738912324546ik4最長(zhǎng)單調(diào)遞增子序列用數(shù)組b[0:n-1]記錄以a[i](0最長(zhǎng)單調(diào)遞增子序列intmain(){ intn; scanf("%d",&n); inta[100]; for(inti=0;i<n;i++) scanf("%d",&a[i]); printf("%d\n",LISdyna(a,n));}樣例輸入8651581701552393002073895最長(zhǎng)單調(diào)遞增子序列intmain(){樣例輸入5最長(zhǎng)單調(diào)遞增子序列intmain(){ intn; scanf("%d",&n); inta[100]; for(inti=0;i<n;i++) scanf("%d",&a[i]); printf("%d\n",LISdyna(a,n));}intLISdyna(inta[],intn){ intb[100]={0}; inti,j; b[0]=1; for(i=1;i<n;i++){ intk=0; //0~i-1之間，b的最大值 for(j=0;j<i;j++) if(a[j]<=a[i]&&k<b[j])k=b[j]; b[i]=k+1; } intmax=0; for(i=0;i<n;i++) if(b[i]>max)max=b[i]; returnmax;}6最長(zhǎng)單調(diào)遞增子序列intmain(){intLISdy編輯距離問題設(shè)A和B是2個(gè)字符串。要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。這里所說(shuō)的字符操作包括：刪除一個(gè)字符；插入一個(gè)字符；將一個(gè)字符改為另一個(gè)字符。 將字符串A變換為字符串B所用的最少字符操作數(shù)稱為字符串A到B的編輯距離，記為d(A,B)。試設(shè)計(jì)一個(gè)有效算法，對(duì)任給的2個(gè)字符串A和B，計(jì)算出它們的編輯距離d(A,B)。編程任務(wù)： 對(duì)于給定的字符串A和字符串B，編程計(jì)算其編輯距離d(A,B)。7編輯距離問題設(shè)A和B是2個(gè)字符串。要用最少的字符操作將編輯距離問題數(shù)據(jù)輸入： 第一行是字符串A，第二行是字符串B。結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，輸出編輯距離d(A,B)。輸入文件示例fxpimuxwrs輸出文件示例58編輯距離問題數(shù)據(jù)輸入：8編輯距離問題設(shè)所給的2個(gè)字符串為A[1…m]和B[1…n]，定義:D[i,j]=δ(A[1…i],B[1…j])，單字符a,b之間的距離為：考察從字符串A[1…i]到字符串B[1…j]的變換：字符A[i]改為字符B[j]，需要δ(A[i],B[j])次操作；刪除字符A[i]，需要1次操作；插入字符B[j]，需要1次操作。因此，D[i,j]遞歸計(jì)算如下：D[i,j]=min{D[i-1,j-1]+δ(A[i],B[j]),

D[i-1,j]+1,

D[i,j-1]+1}D[i,j]的初始值為：D[i,0]=i,i=0~m;D[0,j]=j,j=0~n9編輯距離問題設(shè)所給的2個(gè)字符串為A[1…m]和B[1…n]，編輯距離問題計(jì)算δ(A,B)的動(dòng)態(tài)規(guī)劃算法：functionEdit_Distance(A,B,m,n):integer;begin fori:=1tomdoD[i,0]:=i; forj:=1tondoD[0,j]:=j; fori:=1tomdo forj:=1tondo begin D[i,j]:=∞; ifA[i]=B[j]thenδ:=0elseδ:=1; ifD[i,j]>D[i-1,j-1]+δthenD[i,j]=D[i-1,j-1]+δ; ifD[i,j]>D[i-1,j]+1thenD[i,j]=D[i-1,j]+1; ifD[i,j]>D[i,j-1]+1thenD[i,j]=D[i,j-1]+1; end;

Edit_Distance:=D[m,n]end;{Edit_Distance}10編輯距離問題計(jì)算δ(A,B)的動(dòng)態(tài)規(guī)劃算法：10編輯距離問題afxpium長(zhǎng)度：mbxwrs長(zhǎng)度：nd12345刪除一個(gè)字符； del插入一個(gè)字符； y將一個(gè)字符改為另一個(gè)字符。 z11編輯距離問題afxpium長(zhǎng)度：mbxwrs長(zhǎng)度：nd123編輯距離問題chara[100],b[100];scanf("%s%s",a,b);intm=strlen(a);intn=strlen(b);intd[101];inti,j;for(i=1;i<=n;i++) d[i]=i;for(i=1;i<=m;i++){ inty=i-1; for(j=1;j<=n;j++){ intx=y; y=d[j]; intz=j>1?d[j-1]:i; intdel=a[i-1]==b[j-1]?0:1;

d[j]=min(x+del,y+1,z+1);

}}printf("%d\n",d[n]);xwrsid[1]d[2]d[3]d[4]f11234x21234p32234i43334u54444m65555刪除一個(gè)字符； del插入一個(gè)字符； y將一個(gè)字符改為另一個(gè)字符。 z12編輯距離問題chara[100],b[100];xwrsi數(shù)字三角形問題 給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如下圖所示。 試設(shè)計(jì)一個(gè)算法，計(jì)算出從三角形的頂至底的一條路徑，使該路徑經(jīng)過(guò)的數(shù)字總和最大。

7 38 810 2744 45265編程任務(wù)： 對(duì)于給定的由n行數(shù)字組成的數(shù)字三角形，編程計(jì)算從三角形的頂至底的路徑經(jīng)過(guò)的數(shù)字和的最大值。13數(shù)字三角形問題 給定一個(gè)由n行數(shù)字組成的數(shù)字三角形如下圖所示數(shù)字三角形問題數(shù)據(jù)輸入： 第1行是數(shù)字三角形的行數(shù)n，1≤n≤100。接下來(lái)n行是數(shù)字三角形各行中的數(shù)字。所有數(shù)字在0~99之間。結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，第1行中的數(shù)是計(jì)算出的最大值。輸入示例

5738810274445265輸出文件示例 3014數(shù)字三角形問題數(shù)據(jù)輸入：14數(shù)字三角形問題for(introw=n-2;row>=0;row--)for(intcol=0;col<=row;col++) if(triangle[row+1][col]>triangle[row+1][col+1]) triangle[row][col]+=triangle[row+1][col]; elsetriangle[row][col]+=triangle[row+1][col+1];

7 38 810

2744 45265row0n-2n-1col(row+1,col+1)(row+1,col)15數(shù)字三角形問題for(introw=n-2;row>=租用游艇問題長(zhǎng)江游艇俱樂部在長(zhǎng)江上設(shè)置了n個(gè)游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i到游艇出租站j之間的租金為r(i,j),1<=i<j<=n。試設(shè)計(jì)一個(gè)算法，計(jì)算出從游艇出租站1到游艇出租站n所需的最少租金。編程任務(wù)： 對(duì)于給定的游艇出租站i到游艇出租站j之間的租金為r(i,j),1<=i<j<=n，編程計(jì)算從游艇出租站1到游艇出租站n所需的最少租金。16租用游艇問題長(zhǎng)江游艇俱樂部在長(zhǎng)江上設(shè)置了n個(gè)游艇出租站1租用游艇問題數(shù)據(jù)輸入： 第1行中有1個(gè)正整數(shù)n（n<=200），表示有n個(gè)游艇出租站。接下來(lái)的n-1行是r(i,j),1<=i<j<=n。結(jié)果輸出: 程序運(yùn)行結(jié)束時(shí)，輸出從游艇出租站1到游艇出租站n所需的最少租金。輸入示例35157輸出示例12123515717租用游艇問題數(shù)據(jù)輸入：1235input:7131524442950161882153726438121299411Output:25租用游艇問題12345671315244429501234567113152444295021618821533726438412129594611718input:租用游艇問題123租用游艇問題01234560131524442950116188215327264383121294945116123456013152221192510161881712200719415300012112400009450000011i=1p=2j=5i=1p=3j=5i=1p=4j=5123456013152221295010161881753200719438300012112400009450000011i=1p=2j=4i=1p=3j=4123456013152244295010161882153200719438300012129400009450000