2019-10-11

动态规划

动态规划：
　　简单的说就是，大问题化解为小问题，然后小问题解决后组装成大问题，可以压缩解决大问题的时间。

动态规划和递归的区别：
　　我自己学的时候，我对动态规划的感觉就是这明明就是递归嘛，但是当我解决了几道题之后发现还是有一定区别。
　　两种想法都是将大问题分解为小问题，使用类似于分而治之的思想去解决问题。
　　以斐波拉契数列为例，递归要算F(n)=F(n-1)+F(n-2);(n>2)就需要算n-1和n-2的解，依次解决的话就会重复计算中间的值，会导致计算量变大；而动态规划的话，会减少计算重复值，更优化。

举例：

一、斐波拉契数列
　　题目：兔子繁殖问题：
　　这是一个有趣的古典数学问题，著名意大利数学家Fibonacci曾提出一个问题：有一对小兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律，假设没有兔子死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？
　　这就是著名的斐波那契数列（Fibonacci sequence），该数列，又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
　　特点：这个数列从第3项开始，每一项都等于前两项之和。
　　思路：
　　①递归：从第二项开始 F(n)=F(n-1)+F(n-2);
　　②动态规划：定义left,right以及sum三个变量，通过不断地更新和移位算出接下来的值，可以避免递归的重复计算。

　　具体实现：
　　①递归：

import java.util.Scanner;
public class FeiBoNaQie {
    public static void main(String[] args) {
    	Scanner input=new Scanner(System.in);
    	int n=input.nextInt();
    	int[] a=new int[n];
    	a[1]=a[0]=1;
        System.out.println(FB(n));
    } 
    public static int FB(int n) {  
    	if(n<=1)   //输入为0/1输出结果为0/1
        	  return n;
    	else
          return FB(n-1)+FB(n-2);  //不断递归公式
    }    
}

　　代码结果：
　　！

　　②动态规划：

import java.util.Scanner;
public class FeiBoNaQie {
    public static void main(String[] args) {
    	Scanner input=new Scanner(System.in);
    	int n=input.nextInt();
    	int[] a=new int[n];
        System.out.println(FB(n-1));
    } 
    public static int FB(int n) {
        if(n<=1)
        	return n;
        int left=1,right=1;
        int sum=0;
        for(int i=2;i<=n;i++)  //从第三个开始（0开始）为前两个之和
        {	
        	sum=left+right;  //第三个为第一个数和第二个数之和
        	right=left;    //第一个数指向第二个数位置
        	left=sum;   //第三个数字指向第一个数位置
        }
		return sum; 	 	
    }    
}

　　代码结果：
　　！

二、跳台阶
　　题目：
　　一只青蛙一次可以跳上一级台阶，也可以跳上两级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
　　思路：
　　首先考虑需要跳两级台阶，那么第一种情况就是一次跳两级，第二种是一次跳一级。
　　那么如果需要跳n级台阶，把跳法记作函数f(n):当n>2时，一是第一次跳一级，那么剩下的n-1级就需要f(n-1)。
二是第一次跳两级，那么剩下的n-2级就需要f(n-2)。所以整理可知，这实际上也是一个斐波拉数列！

　　具体实现：

import java.util.Scanner;
public class TiaoTaiJie {
    public static void main(String[] args) {
    	Scanner input=new Scanner(System.in);
    	int n=input.nextInt();
    	int[] a=new int[n];
        System.out.println(TaiJie(n-1));
    } 
    public static int TaiJie(int n) {
        if(n<=1)
        	return n;
        int left=1,right=1;
        int sum=0;
        for(int i=2;i<=n;i++)  //从第三个开始（0开始）为前两个之和
        {	
        	sum=left+right;  //第三个为第一个数和第二个数之和
        	right=left;    //第一个数指向第二个数位置
        	left=sum;   //第三个数字指向第一个数位置
        }
		return sum; 	
    }    
}

　　代码结果：
　　！

三、变态跳台阶
　　题目：
　　在上题目的基础上，这次一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶….也可以跳上n级台阶。求青蛙上一个n级台阶总共有多少跳法。
　　思路：
　　我们可以依旧从最简单的二级开始考虑：
　　如果我们需要跳上2级台阶，那么第一种方法是跳二级台阶，第二种是一次一级。
　　如果是n级台阶，那么可以从n-1级跳一级上去，也可以从n-2级跳两级上去：
　　因此 f(n)=f(n-1)+f(n-2)+…+f(1); （1）
　　如果是n-1级台阶，那么可以从n-2级跳一级上去，也可以从n-3级跳两级上去：
　　因此 f(n-1)=f(n-2)+f(n-3)+…+f(1); （2）
　　则(1)和(2)式联立，我们可以得出f(n)=2*f(n-1);

　　具体实现：

import java.util.Scanner;
public class BianTaiTiaoTaiJie {
    public static void main(String[] args) {
    	Scanner input=new Scanner(System.in);
    	int n=input.nextInt();
    	int[] a=new int[n];
        System.out.println(BianTai(n));
    } 
    public static int BianTai(int n) {  
    	if(n==1)
    		return 1;  //需要跳一级只有一种方法
    	if(n==2)
    		return 2;  //需要跳二级有两种方法
    	else
    		return 2*BianTai(n-1)；/return (int)Math.pow(2,n-1);  //需要跳n级有n-1种方法（不断求解）
    }    
}