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

对于这道题,我第一眼看到的想法是用递归的做法的,用递归的方法做题,我觉得最重要的就是找出 这个函数与下一个函数之间的关系 以及 一个函数体结束的临界条件(即递归的结束)。

例如就本题而言,

1.第一步先找这个函数与下一个函数之间的关系:

假如有n个台阶,跳上一个n级的台阶的跳法总数为f(n).

我们在跳的过程中,每一次有两种跳法,即跳一个或两个台阶。

第一种跳法:第一次跳了一个台阶,那么还剩下n-1个台阶还没跳,剩下的n-1个台阶的跳法有f(n-1)种。

或者用

第二种跳法:第一次跳了两个台阶,那么还剩下n-2个台阶还没跳,剩下的n-2个台阶的跳法有f(n-2)种。

由此不难得出递归公式:f(n) = f(n-1) + f(n-2);

2.第二步,找出递归的结束条件

当n <= 0时,跳法为0,即此时f(n) = 0

当只剩下一个台阶n = 1时,那么只有一种跳法,即f(1) = 1;

当n = 2时,此时跳法为2种,即f(2) = 2;

函数与函数之间的关系以及递归的临界条件都找出来了,那么接下来就可以开始写代码了。如下所示:

package com.bupt.practice;

/** * Created by zyx on 2019/3/28. **/


public class Frog_jumping_stairs_1 {

    public static int f(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n <= 0) {
            return 0;
        } else {
            return f(n - 1) + f(n - 2);
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();   //获取开始时间
        int x = f(40);
        System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//480ms
    }
}

不过观察一下你就会发现,其实在递归的过程中,有很多相同的)f(n)重复算。

如下图:

算一下你就知道,时间复杂度是指数级别的。如果是比赛这样做的话,绝对超时不通过。

因此对于那些重复算过的,其实我们可以不用在重复递归来算它的,也就是所我们可以把f(n)算的结果一边给保存起来,这种就是动态规划的思想。

也就是说,我们可以把每次计算的结果保存中一个map容器里,把n作为key,f(n)作为value.然后每次要递归的时候,先查看一下这个f(n)我们是否已经算过了,如果已经算过了,我们直接从map容器里取出来返回去就可以了。如下:

package com.bupt.practice;

/** * Created by zyx on 2019/3/28. **/

import java.util.*;

public class Frog_jumping_stairs_2 {
	//采用动态规划的方法
    static Map<Integer, Integer> map = new HashMap<>();

    public static int f1(int n) {
        if (n <= 0) {
            return 0;
        } else if (n <= 2) {
            return n;
        } else {
            if (map.containsKey(n)) {//查看是否存在
                return map.get(n);
            } else {//如果不存在则递归运算
                int m = f1(n - 1) + f1(n - 2);
                map.put(n, m);//保存起来
                return m;
            }

        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();   //获取开始时间
        int x = f1(40);
        System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//19ms
    }
}

这种方***快很多很多。

实际上,对于f(n) = f(n-1) + f(n - 2)这种有递推关系的题,其实和斐波那契数列很相似,还可以这样做:

package com.bupt.practice;

/** * Created by zyx on 2019/3/28. **/

public class Frog_jumping_stairs_3 {
    public static int f3(int n) {
        if (n <= 0) {
            return 0;
        } else if (n <= 2) {
            return n;
        }
        int f0 = 0;
        int f1 = 1;
        int f2 = 2;
        int sum = 0;
        for (int i = 3; i <= n; i++) {
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();   //获取开始时间
        int x = f3(40);
        System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//17ms

    }
}

问题2: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法?

分析,其实这道题和上面那道题一样的,只是本来每次跳有两种选择,现在有n中选择,即f(n) = f(n-1) + f(n - 2) + f(n-3)+…+f(1);

因此做法如下:

package com.bupt.practice;

/** * Created by zyx on 2019/3/28. **/

import java.util.*;

public class Frog_jumping_stairs_4 {
    static Map<Integer, Integer> map = new HashMap<>();

    public static int f4(int n) {
        if (n <= 0) {
            return 0;
        } else if (n <= 2) {
            return n;
        } else {
            if (map.containsKey(n)) {
                return map.get(n);
            } else {
                int m = 0;
                for (int i = 1; i < n; i++) {//相当于f(n) = f(n-1)+f(n-2)+…+f(1);
                    m += f4(n - i);
                }
                map.put(n, m);
                return m;
            }
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();   //获取开始时间
        int x = f4(30);
        System.out.println("总共有" + x + "种跳法");//总共有165580141种跳法
        long endTime = System.currentTimeMillis(); //获取结束时间
        System.out.println("程序运行时间: " + (endTime - startTime) + "ms");//16ms
    }

}

转载于:

递归与动态规划—基础篇1