计算概论 动态规划
计算概论计算概论第十五讲 动态规划内容提要内容提要?为什么要用动态规划的方法?递归程序转化为动态规划程序?例题树形递归树形递归?例1：POJ 2753 Fibonacci数列?1，1，f(n-1)+f(n-2), int f(int n) if(n=0 | n=1) return 1; return f(n-1)+f(n-2); f(5)f(3)f(2)f(1)f(2)f(4)f(3)f(0) f(1)f(0)f(2)f(1) f(1)f(0)f(1)11001010冗余计算冗余计算?POJ 2753 Fibonacci数列 计算过程中存在冗余计算，为了出去冗余计算 可以从已知条件开始计算，并记录计算过程中 的中间结果。?POJ 2753 Fibonacci数列 int fn+1; f1=f2=1; int I; for(i=3;i 动态规划动态规划的实质?动态规划的实质就是动态规划的实质就是就是将用搜索解决时会重复计算的值，算好一次后就存 起来，以后不必重新计算，用空间换时间。就是将用搜索解决时会重复计算的值，算好一次后就存 起来，以后不必重新计算，用空间换时间。动态规划动态规划?例2 POJ 1163 数字三角形在上面的数字三角形中寻找一条从顶部到底边的路径，使得路径 上所经过的数字之和最大。路径上的每一步都只能往左下或右 下走。只需要求出这个最大和即可，不必给出具体路径。 三角形的行数大于1小于等于100 数字为 0 - 997 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输入格式：5/三角形行数。下面是三角形 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 要求输出最大和?算法一：递归的想法 设f(i,j) 为三角形上从点(i,j)出发向下走的最长路 经，则 f(i,j) = max(f(i+1,j), f(i+1,j+1) 要输出的就是f(0,0)即从最上面一点出发的最长 路经。?代码如下：#include #define MAX 101 int triangleMAXMAX; int n; int longestPath(int i, int j); void main() int i,j; cin >> n; for(i=0;i> triangleij; cout #define MAX 101 int triangleMAXMAX, n; void main() int i,j; cin >> n; for(i=0;i> triangleij; for(i=n-2;i>=0;i-)for(j=0;j #include #define MAX 1000 char str1MAX, str21000; int commonstr(int,int); void main() while(cin >> str1 >> str2) int len1=strlen(str1); int len2=strlen(str2); cout tmp2) return tmp1; else return tmp2; 超时！?算法二：动态规划 从str1和str2的第一个字符开始考虑； int commonLengthMAXMAX; 用一个二维数组记录str1的前i个字符与str2中的前j个 字符的最大公共子串长度?设立初值：comLen 00MAX=0;comLen 0MAX0=0; 表示两个字符串中有一个没有参与比较时，最大公 共子串长度为?递推：if(stri=strj) comLen ij =1+ comLen i-1j-1; else comLenij = max(comLeni-1j,comLenij- 1);#include #include #define MAX 1000 char str1MAX,str2MAX; int comMAXMAX, i, j; void main() while(cin >> str1 >> str2) int len1=strlen(str1); int len2=strlen(str2); for(i=0;icomij-1) comij=comi-1j; else comij=comij-1; /else /forcout void main() int n,i,j,k,count40=0; cin >> n; int numbers21; for(i=0;i> numbersi; for(i=1;i0; j>>=1,k-) if(j if(sum=40) count40+; cout #include int N; int v30; int WayNumber(int nDone, int w) int nResult = 0; if( w = 0 ) return 1; for( int i = nDone; i > N; int i; for( i = 0;i > vi; cout #include const int MaxN = 21; int N; int v30; int WayNumberMaxN41; main() int i; cin >> N; for( i = 0;i > vi; memset( WayNumber,0,sizeof(WayNumber); for( i = 0; i = 0; i - ) for( int j = 1; j #define MAX 41 void main() int n,i,j,input; int sumMAX; for(i=0;i> n; for(i=0;i> input; for(j=40;j>=1;j-) if(sumj>0 suminput+; cout << sum40 << endl;
