ACM培训-动态规划

《ACM培训-动态规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ACM培训动态规划动态规划的概念¢动态规划算法通常用来解决最优化问题。这些问题可能存在多个解，每个解具有一个值。我们希望找到一个具有最优（最大或最小）值的解。在动态规划算法中，主要关心的是找到一个最优解和求出最优解的值，而不是找出所有的最优解。例：计算斐波那契数：⎧0n=0⎪F(n)=⎨1n=1⎪⎩F(n−1)+F(n−2)n≥2n=5时分治法计算斐波那契数的过程。F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)算法0#include

2、ream>usingnamespacestd;intf(intn){if(n==1

3、

4、n==0)return1;elsereturnf(n-1)+f(n-2);}缺点:重复计算,浪费时间main(){intn;cin>>n;cout<

5、m>usingnamespacestd;intsave[100];intf(intn){if(save[n]!=0)returnsave[n];if(n==1

6、

7、n==0){save[n]=1;returnsave[n];}save[n]=f(n-1)+f(n-2);returnsave[n];}main(){memset(save,0,sizeof(save));intn;cin>>n;cout<

8、化,正符合了这个要求.用动态规划法求解的问题具有特征：V能够分解为相互重叠的若干子问题；V满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。∑动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。数字三角形¢给你一个数字三角形,形式如下:1234

9、5678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形的演化¢给你一个数字三角形,形式如下:12345678910找出从第一层到最后一层的一条路,使得所经过的权值之和最小或者最大.数字三角形¢状态转移方程：¢f(i,j)=a[i,j]+min{f(i-1,j)+f(i-1,j+1)}¢正面思路分析问题，得出一个非常简单的递归过程:¢f1=f(i-1,j+1);f2=f(i-1,j);¢if(f1>f2)f=f1+a[i,j];elsef=f2+a[i,j];算法0#include

10、usingnamespacestd;#definemax100inta[max][max];intsum(inti,intj,intn){if(i==n-1)returna[i][j];else{if(sum(i+1,j,n)>sum(i+1,j+1,n))returnsum(i+1,j,n)+a[i][j];elsereturnsum(i+1,j+1,n)+a[i][j];}}main(){inti,j,t;缺点:重复计算,浪费时间intn;cin>>n;for(i=0;i

11、(j=0;j<=i;j++)cin>>a[i][j];cout<

12、直观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，#includeusingnamespacestd;算法1#definemax100inta[max][max];intopt[max][max];intsum(inti,intj,intn){if(opt[i][j]!=0)returnopt[i]