admin 管理员组文章数量: 894082
动态规划法例题
动态规划:存储记忆,减少计算量
1、斐波那契数列
动态规划法:n输入的数字大时(如60)比递归法计算速度快很多
public int fib(int n,HashMap<Integer,Integer> map) {if(n==0){return 0;}else if(n==1){return 1;}else if (map.containsKey(n)){return map.get(n);}else {int x=fib(n-1,map)+fib(n-2,map);//x不会立刻算出,而是会递归到fib(2)=fib(1)+fib(0)并存储map.put(n,x);//把中间计算的fib(n-1)+fib(n-2)存储起来,方便后面直接查找而不用递归到fib(0)和fib(1)return x;}}
此外,换个角度思考,斐波那契数列仅与前两个有关,我们又可得知最开始的两个,那么我们可以实行推进滚动的思路
public int fib(int n) {if(n<2){return n;}int p=0,q=1,r=1;//最开始p指向fib(0),q指向fib(1),r指向fib(2)for(int i=2;i<=n;i++){r=p+q;p=q;q=r;}return r;}
2、爬楼梯问题
假设你正在爬楼梯。需要 n
阶你才能到达楼顶。
每次你可以爬 1
或 2
个台阶。你有多少种不同的方法可以爬到楼顶呢?(1<=n<=45)
倒着看,最后一步可能迈一个台阶也可能迈俩台阶,那么总体情况就是这俩加起来即
f(n)=f(n-1)+f(n-2),又变成了和斐波那契数列一样
public int climbStairs(int n) {if(n<=2){return n;}else {int p=1,q=2,r=0;for(int i=3;i<=n;i++){r=p+q;p=q;q=r;}return r;}}
3、走方格问题
请计算n*m的棋盘格子(n为横向的格子数,m为竖向的格子数)从棋盘左上角出发沿着边缘线从左上角走到右下角,总共有多少种走法,要求不能走回头路,即:只能往右和往下走,不能往左和往上走。
注:沿棋盘格之间的边缘线行走
数据范围: 1≤n,m≤8
只能是正上和左上,用二维数组储存到某一个点处的方案数
import java.util.Scanner;public class Main {public static int fun(int n,int m){int[][] arr =new int[m+1][n+1];//m+1行,n+1列arr[0][0]=0;//左上角放值for(int i=1;i<=n;i++){//第一行放值arr[0][i]=1;}for(int i=1;i<=m;i++){//第一列放值arr[i][0]=1;}for (int i=1;i<=m;i++){//行for (int j=1;j<=n;j++){//列arr[i][j]=arr[i-1][j]+arr[i][j-1];}}return arr[m][n];}public static void main(String[] args) {Scanner scanner =new Scanner(System.in);int n=scanner.nextInt();int m= scanner.nextInt();System.out.println(fun(n,m));}
}
4、放苹果问题
把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?
注意:如果有7个苹果和3个盘子,(5,1,1)和(1,5,1)被视为是同一种分法。
数据范围:0≤m≤10 ,1≤n≤10 。
import java.util.Scanner;public class Main {public static int fun(int m,int n){//m个苹果,n个盘子int[][] arr = new int[n+1][m+1];for(int i=0;i<=m;i++){//第0行置为0,arr[0][i]=0;}for(int i=1;i<=n;i++){//第0列置为1,arr[i][0]=1;}for(int i=1;i<=n;i++){//i是盘子,j是苹果for (int j=1;j<=m;j++){if(j>=i){arr[i][j]=arr[i-1][j]+arr[i][j-i];}else {arr[i][j]=arr[i-1][j];}}}return arr[n][m];}public static void main(String[] args) {Scanner scanner =new Scanner(System.in);int m=scanner.nextInt();int n= scanner.nextInt();System.out.println(fun(m,n));}
}
本文标签: 动态规划法例题
版权声明:本文标题:动态规划法例题 内容由网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:http://www.freenas.com.cn/jishu/1687605012h120230.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论