DP动态规划ACM课件

1、DP动态规划ACM课件 DP动态规划ACM课件 DP是在20世纪50年代由一位卓越的美国数学 家Richcard Bellman发明的。它作为一种重 要的工具在应用数学中被广泛的应用。它不 仅可以解决特定类型的优化问题，还可以作 为一种通用的算法设计技术来使用。 DP动态规划ACM课件 DP的实质 利用问题的所具有的重叠子问题的性质进行 记忆化求解。（用空间换时间） DP动态规划ACM课件 求Fibonacci数： f(n) = f(n-1) + f(n-2) n2 f(1)=f(2)=1 DP动态规划ACM课件 常规递归 int Non_DP(int n) if (n=1 | n=2) re

2、turn 1; else return Non_DP(n-1) + Non_DP(n-2); 指数级时间复杂度，无法忍受 DP动态规划ACM课件 两种实现方式 自底向上(bottom up) int DP_Bottom_Up(int n) memo1 = memo2 = 1; for (int i=3; i=n; i+) memoi = memoi-1 + memoi-2; return memon; DP动态规划ACM课件 自顶向下（top down） int DP_Top_Down(int n) if (n = 1 | n = 2) return 1; if (memon != 0) re

3、turn memon; memon = DP_Top_Down(n-1) + DP_Top_Down(n-2); return memon; DP动态规划ACM课件 基本概念 最短路问题 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 求A到E的最短路径。 DP动态规划ACM课件 直观的方法是用回溯法搜索。时间复杂度为 指数级。 低效的原因：没有充分利用重叠子问题的性 质。 DP动态规划ACM课件 此图有明显的次序，可以划分为5阶段。 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 阶段0阶段1阶段2阶段3阶段4 DP动态规划ACM课件 设 Diskx 为第k阶段城

4、市x到城市E的最短路径长度。 map i j 为i，j两个城市间的距离。 递归方程为 Diskx = min Disk+1y+mapx,y 此问题时间复杂度降为O(n2). DP动态规划ACM课件 状态：贴切，简洁的描述出事物性质的单元量。例如： Disx。 要求：状态与状态之间可以转移，以便有初始状态逐渐转移 到目标状态，找到问题的解。 阶段：若干性质相近可以同时处理的状态的集合。就是计算 状态的顺序。 要求：每个阶段中状态的取值只与这个阶段之前的阶段中的 状态有关，与这个阶段之后的阶段中的状态无关。 DP动态规划ACM课件 状态转移方程：前一个阶段中的状态转移到后一个 阶段的状态得演变规律

5、，即相邻两个阶段的状态变 化方程。 fk(i) = opt fk-1(j) + cost(i,j) k阶段的i状态与k-1阶段的j状态有关 决策：计算每个状态时作出的选择。 DP动态规划ACM课件 适合用DP解决的问题的性质 最优子结构:若求解的问题是最优化问题，则原问题 最优当且仅当自问题最优。 Mod 4 最优路径问题 找出1到4的一条长度mod 4的余数最小的路径。 123 4 DP动态规划ACM课件 此最优化问题不满足最优子结构，所以不适合用DP。 但如果我们增加状态的维数，将最优化问题转化成 判定性问题，再运用DP，问题就可得以解决。 设 fki 为bool型数组，表示从1点到k点长

6、度mod4 为i的路径是否存在。 fki= fk-1i-lenk1 | fk-1i-lenk2 | | fk-1i-lenkn DP动态规划ACM课件 无后效性：决策之取决于当前状态的特征因 素，而和到达此状态的方式无关。也就是每 个阶段中状态的取值只与这个阶段之前的阶 段中的状态有关，与这个阶段之后的阶段中 的状态无关。 如果当前定义的状态不满足无后效性，应重 新定义。 DP动态规划ACM课件 一维状态存储问题 硬币问题1： 有n种硬币，每种硬币的面值为vi元，且只有一 枚，问用这n种硬币找零S元的方法数。 设dij为前i种硬币组成j元的方法数。 dij = di-1j + di-1j-vi

7、 d00=1,d01S=0 空间复杂度为O(n2),浪费！ DP动态规划ACM课件 d0=1; d1S=0; for (i=1; i=vi; j-) dj += dj-vi; DP动态规划ACM课件 0-1背包问题： 给定n种物品和一背包。物品i的重量是wi， 其价值为vi，背包的容量为c。问应如何选 择装入背包中的物品，使得装入背包中物品 的总价值最大? DP动态规划ACM课件 设m(i,j)是背包容量为j，可选择物品为i， i+1，,n时，0-1背包问题的最优值。 m(i,j) = max m(i+1,j), m(i+1,j-wi)+vi j=wi m(i+1,j)0=jwn 0 i=jw

8、n DP动态规划ACM课件 d0c=0; for (i=1; i=wi; j-) dj = max(dj,dj-wi+vi); DP动态规划ACM课件 推荐题目： POJ1384 Piggy-Bank DP动态规划ACM课件 POJ1384参考代码 #include using namespace std; int d100052; /第2维用0表示标记，1表示钱的值 int main() int x,y,weight; int w,m; int i,j,t,n; scanf(%d, while(t-) scanf(%d%d, weight=y-x; memset(d,0,sizeof(d);

9、 d00=1; /重要的初值 scanf(%d, for(i=1;i=n;i+) /阶段 scanf(%d%d, for(j=0;j=weight-w;j+) /枚举 if(dj0=1) /当前有，才可以叠加到后一层 x=j+w; if(dx0=0) dx1=dj1+m; else dx1=min(dx1,dj1+m); /最重要的比较部分！ dx0=1; if (dweight0=1) printf (The minimum amount of money in the piggy-bank is %d.n,dweight1); else printf (This is impossible

10、.n); return 0; DP动态规划ACM课件 硬币问题2： 有n种硬币，每种硬币的面值为vi元，有mi 枚，问用这n种硬币找零S元的方法数。 DP动态规划ACM课件 d0=1;d1S=0; for (i=1; i=vi; j-) for(k=1;k=0) dj += dj-k*vi; DP动态规划ACM课件 硬币问题3： 有n种硬币，每种硬币的面值为vi元，有无 数枚，问用这n种硬币找零S元的方法数。 DP动态规划ACM课件 d0=1;d1S=0; for (i=1; i=vi; j-) for(k=1;k+) if (j-k*vi=0) dj += dj-k*vi; else bre

11、ak; DP动态规划ACM课件 d0=1; d1S=0; for (i=1; i=n; i+) for (j=vi;j=S; j+) dj += dj-vi; DP动态规划ACM课件 POJ2614 Old Wine Into New Bottles 有n种小瓶子，每种瓶子容量范围是Vi1Vi2，要 灌满容量为L的大瓶子。问最少差多少体积没有灌 满。 设di表示体积为i是否可以达到。若v可取到，则 di=di | di-v DP动态规划ACM课件 d0=1;d1L=0; for(i=0;in;i+) for(j=0;j=L-vi1;j+) if (dj=1) for(k=vi1;k=vi2;k

12、+) dj+k=1; DP动态规划ACM课件 POJ2614参考代码 #include using namespace std; int f450001=0,v1022; bool fff4600; int main() int i,j,k; int l,n; int ff=1; while(scanf(%d%d,i= 450000) printf(0n);continue; memset(f,0,sizeof(int)*(l+1); memset(fff,0,sizeof(fff); f0=1; for(i=1;i=n;i+) for(k=vi0;k=vi1;k+) if(fffk) con

13、tinue; for(j=0;j=l-k;j+) fffk=1; if(fj) fj+k=1; if(fl) goto out; out: for(i = 0;i = l; i+) if(fl-i) printf(%dn,i); break; return 0; DP动态规划ACM课件 最大子段和问题： 给定由n个整数(可能为负整数)组成的序列 a1,a2,an，求该序列形如的 子段和的 最大值。 j ik ka DP动态规划ACM课件 设bi为到ai截至且包括ai的字段最大和。 int maxsum() int sum=0,b=0; for(int i=0;i0) b+=ai; /正的就连接

14、起来 else b=ai;/不然重新来过 if (bsum) sum=b;/sum记录的一直是最大的值 return sum; DP动态规划ACM课件 引申问题： 最大子矩阵和问题 最大m段子段和问题 DP动态规划ACM课件 最长递增子序列（LIS） 常规DP，时间复杂度为O(n2)。 存在一种特殊的方法，时间复杂度为 O（n*logk)。 DP动态规划ACM课件 推荐题目： POJ1631 Bridging Signals DP动态规划ACM课件 POJ1631参考代码 #include using namespace std; int d40001; int main() int n,t;

15、 int i,p,num; int high,low,x; scanf(%d, while( t-) scanf(%d, scanf(%d, p=1; for(i=2;idp) p+;dp=num;continue; high=p,low=1; for(;highlow+1;) x=(high+low)/2; if(numdx) low=x; else if(numdx) high=x; if(numdlow) dhigh=num; else if(numdlow) dlow=num; printf(%dn,p); return 0; DP动态规划ACM课件 二维状态存储问题 矩阵连乘问题矩阵

16、连乘问题 （MCM） A(m*n) * B(n*q) cost=m*n*q A1 (10 x 100), A2 (100 x 5), A3 (5 x 50) (A1 (A2 A3) = 100 x 5 x 50 + 10 * 100 * 50 = 75000 (A1 A2) A3) = 10 x 100 x 5 + 10 x 5 x 50 = 7500 DP动态规划ACM课件 最优子结构： DP动态规划ACM课件 重叠子问题： DP动态规划ACM课件 状态转移方程： DP动态规划ACM课件 阶段划分： DP动态规划ACM课件 推荐题目： POJ1141 Brackets Sequence DP动态规划ACM课件 POJ1141参考代码 #include #include using namespace std; int n,l; string str; int opt101101; string ds101101; char ss101; void dynamic() int i,j,k,p; for(i=1;i=l;i+) optii=1; optii-1=0; dsii-1=; if (stri=( | stri=