admin 管理员组文章数量: 893559
算法设计之动态规划法
算法设计之动态规划法
- 一、目的
- 二、内容
- 1.斐波那契数列
- ①自底向上
- 分析
- 解决
- ②自顶向下
- 分析
- 解决
- 2.走棋盘问题
- 分析
- 解决
- 3.爬台阶问题
- 分析
- 解决
- 三、反思与总结
一、目的
1.理解动态规划法的特征(多阶段决策\最优子结构\无后效性\子问题重复)
2.理解动态规划法的求解(划分过程\逆向推导\正向计算)
3.掌握动态规划法的简单实体(自顶向下递归备忘\自底向上迭 代填表)和时间复杂度分析
二、内容
1.斐波那契数列
①自底向上
分析
斐波拉契数列的递推式为:
求第n个斐波拉契数时,需要知道F(n-1)和F(n-2)的值,可以设计一个表格填入n+1个F(n)的值,开始时,根据初始条件可以直接填入F(1)和F(2),然后根据递推式计算出其他元素,表中最后一项就是F(n)的值。
按此想法,计算第n个斐波拉契数,共需循环n次,可能的时间复杂度为O(n)。
解决
算法描述:
输入:n(所求的项数)
输出:第n个斐波拉契数
int Fib(int n)
1.定义一个数组fib[]储存斐波拉契数列,数 组长度为n+1,初始化为0
2.赋值fib[1] = 1,fib[2] = 1
3.定义变量i,循环变量i从3到n执行下列操作:
3.1 fib[i] = fib[i-1] +fib[i-2]
3.2 i++
4.返回fib[n]的值
int Fib(int n){ // 自底向上迭代填表int fib[n+1];fib[1] = 1;fib[2] = 1;for(int i=3; i<=n; i++){fib[i] = fib[i-1] +fib[i-2];}return fib[n];
}
基本语句为fib[i] = fib[i-1] +fib[i-2],执行次数为
时间复杂度为:O(n)
②自顶向下
分析
在求解第n个斐波拉契数,需要知道F(n-1)和F(n-2)的值,若递归求解,存在子问题重复,降低了算法的效率,所以采用备忘录的方式。使用一个数组充当备忘录,算出某个子问题的解后储存在备忘录中,每次遇到一个子问题先去备忘录中查一查,如果发现已经解决过这个问题了,直接把答案拿出来用,不要再耗时去计算了。
解决
算法描述:
输入:n(所求的项数)
输出:第n个斐波拉契数
int Fib(int n,int fib[])
- 如果n=1,fib[1] = 1,返回fib[1]
- 如果n=2,fib[2] = 1,返回fib[2]
- 否则,执行下列操作
3.1 如果fib[n]不等于0,返回fib[n]
3.2 fib[n] = Fib(n-1,fib) + Fib(n-2,fib)
3.3 返回fib[n]
int Fib(int n,int fib[]){ //自顶向下递归备忘if(n==1){fib[1] = 1;return fib[1];}else if(n==2){fib[2] = 1;return fib[2];}else{if(fib[n]!=0){return fib[n];}}fib[n] = Fib(n-1,fib) + Fib(n-2,fib);return fib[n];
}
时间复杂度为:
2.走棋盘问题
分析
求解从棋盘的第一行第一列走到棋盘的第n行第m列的走法,每次只能向右或向下走
逆向推导:最后一步只能向下或向右走,那么走到棋盘的第n行第m列应该是走到棋盘第n行第m-1列的走法和第n-1行第m列走法的和,即f(n-1,m-1)=f(n-2)(m-1)+f(n-1)(m-2),继续向前推,考虑倒数第二步,若走到第一行或者第一列,只能向左或向上倒推,直到f(0,0)
正向求解f(0,0)=0,f(0,1)=1,f(1,0)=1,…,
f(n-1,m-1)=f(n-2)(m-1)+f(n-1)(m-2)得到原问题的解
按此想法,棋盘共有n行m列,可能的时间复杂度为O(mn)
解决
输入:棋盘有n行,m列
输出:每次只能往右走一步,或者往下走一步,从第1行第1列走到第n行m列不同的走法数
int Chess(int n, int m)
- 定义一个数组a[ n ][ m ];
- 循环变量i从0~n-1时重复执行
2.1 a[ i ] [ 0 ]= 1;
2.2 i++; - 循环变量j从0~m-1时重复执行
3.1 a[ 0 ] [ j ]= 1;
3.2 j++; - 循环变量i从1~n-1时重复执行下列操作
4.1循环变量j从0~m-1时重复执行下列操作
4.1.1 a [ i ][ j ] = a [ i-1 ][ j ] + a [ i ][ j-1 ]
4.1.2 j++;
4.2 i++ - 返回a [ n-1 ][ m-1 ]的值
int Chess(int n, int m)
{int a[n][m];int i,j;for(int i=0; i<=n-1; i++){a[i][0] = 1;}for(int j=0; j<=m-1; j++){a[0][j] = 1;}for(i=1; i<=n-1; i++){for(j=1; j<=m-1; j++)a[i][j] = a[i-1][j] +a[i][j-1];}return a[n-1][m-1];
}
基本语句:a[i][j] = a[i-1][j] +a[i][j-1]
执行次数:
3.爬台阶问题
分析
要爬到第n级台阶,每次可以跨1级或2级,求解一共有多少种走法逆向推导:最后一步可以跨一级或者两级台阶,那么爬到n级台阶的走法应该是爬n-1级台阶的走法和n-2级台阶走法的和,f(n)=f(n-1)+f(n-2),继续向前推,考虑倒数第二步,直到f(1);
正向求解:f(1)=1,f(2)=2,f(3)=f(1)+f(2)=3,…,f(n)=f(n-1)+f(n-2)得到原问题的解。
按此想法,爬到第n级台阶,共需循环n次,可能的时间复杂度为O(n)
解决
输入:要爬的台阶数 int n
输出:爬完n级台阶的走法
int Chess(int n, int m)
- 定义一个数组a[ n ][ m ]
- 定义变量i,循环变量i从0到n-1执行下列循环:
2.1 a[ i ] [ 0 ]= 1
2.2 i++ - 定义变量j,循环变量i从0到m-1执行下列循环:
3.1 a[ 0 ] [ j ]= 1
3.2 j++
4.定义变量i,循环变量i从0到n-1执行下列循环
4.1循环变量j从0~m-1时重复执行下列操作
4.1.1 a [ i ][ j ] = a [ i-1 ][ j ] + a [ i ][ j-1 ]
4.1.2 j++
4.2 i++
5.返回a [ n-1 ][ m-1 ]的值
int ClimbStep(int n){int i;int a[n+1] = {0} ;for(i=1; i<=2; i++){a[i]=i;}for(i=3; i<=n; i++){a[i] = a[i-1] +a[i-2];}return a[n];
}
基本语句:a[i] = a[i-1] +a[i-2]
执行次数:
时间复杂度:O(n)
三、反思与总结
1.如果用分治函数实现斐波那契数列,该函数被调用几次? 而用自顶向下递归备忘实现时,该函数又被调用几次? 自底向上迭代填表时,又被调用几次?请你给出 1 个 n 的具体值,画图回答以上问题。
答:
①分治法(调用 12 次)
②递归备忘(调用 1 次)
③迭代填表(调用 5 次)
2.请从你实现的级别中选择一题,说明动态规划法的解决过程(划分阶段、逆向推导、正向计算),再针对实现说明是自底向上或是自顶向下。
答:
爬台阶(自底向上):
①划分阶段:从第一步依次走到最后一步;
②逆向推导:f(n)=f(n-1)+f(n-2);
③正向计算:f(1)=1;f(2)=1;f(3)=f(1)+f(2)…f(n)=f(n-1)
+f(n-2)
3.你觉得动态规划法和分治法有区别吗?请举例说明。
答:有区别。后者是自顶向下,前者是自底向上解决问题。如实验中对斐波那契数列的两种求解方式。
4.动态规划法的两种实现有区别吗?你觉得动态规划法能解决所有问题吗?
答:有区别。如自底向上迭代法,直接利用递推式,调用一次函数即可求解;而自顶向下备忘法,需要利用递归调用的方式来求解。
动态规划法不能解决所有的问题。适合于用动态规划法求解的问题,经分解后得到的子问题往往不是互相独立的,即下一个子阶段的求解是建立在上一个子阶段的解的基础上,进行进一步的求解。
此文章为作者初学算法时的实验,难免存在错误与不足,恳请各位批评与指正。
本文标签: 算法设计之动态规划法
版权声明:本文标题:算法设计之动态规划法 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687604982h120227.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论