计算概论 动态规划
32页1、计算概论计算概论第十五讲 动态规划内容提要内容提要?为什么要用动态规划的方法?递归程序转化为动态规划程序?例题树形递归树形递归?例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、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,
《计算概论 动态规划》由会员ji****72分享,可在线阅读,更多相关《计算概论 动态规划》请在金锄头文库上搜索。
2024-03-21 1页
2024-03-21 1页
2024-03-15 2页
2024-03-01 2页
2024-03-01 2页
2024-02-28 118页
2024-02-28 152页
2024-02-28 87页
2024-02-28 92页
2024-02-28 96页