一. 动态规划概念

image.png

伪代码：

image.png

重构:

image.png

二. 动态规划案例

2.1 青蛙跳台阶

题目：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

这个题目就是用典型的动态规划算法求解的，青蛙跳上一个n级台阶的跳法（记作f（n）），我们可以从青蛙的最后一步入手，将总的跳法分为两类：1 最后一步跳了一阶。2 最后一步跳了两阶。易得f(n)=f(n-1)+f(n-2);这个就是状态转移方程。

代码:

int numWays(int n){

    //滚动数组
    int head=1,behind=1;
    int sum=0;

    for(int i=0;i<n;i++){
        
        //先求和，在滚动
        sum=(head+behind)%1000000007;
        head=behind;
        behind=sum;
    }
    
    return head;

}

2.2 斐波那契列数

古典问题：
有一对兔子，从出生后第2个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第二十个月的兔子对数为多少？

1个月：1
2个月：2
3个月：3
4个月：5
5个月：8
6个月：13
7个月：21

规律：除了第一个月和第二月以外，其余每个月都是前两个月之和
斐波那契列数

如果不理解，可以参考图解:

image.png

代码:

package Java_study;

/**
 * 
 * @author  只是甲
 * @date    2021-07-01
 * @remark  递归求斐波那契列数
 *
 */
public class recursion2 {
    public static void main(String[] args) {
        System.out.println(method(1, 19));//开始1对兔子，19个月后共有6765对兔子
    }
    
    /**
     * @remark month个月后 init个数量对兔子会发展成为多少对兔子数
     * @param init 初始兔子数量
     * @param month 月份
     * @return 结果兔子数量
     */
    public static int method(int init, int month) {
        //必须要有出口
        //如果是第一个月，只有一对兔子
        if (month == 1) {
            return init;
        } else if (month == 2) {
            return init * 2;
        } else {
            return method(init, month - 2) + method(init, month - 1);
        }
    }

}