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));}
}

本文标签: 动态规划法例题