用两种方法（递归和DP）实现了青蛙跳台阶

50 阅读 0 评论 33 点赞

我是靠谱客的博主大气音响，最近开发中收集的这篇文章主要介绍用两种方法（递归和DP）实现了青蛙跳台阶，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

做了这道题目：

https://www.nowcoder.net/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=13&tqId=11161&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目本身比较简单，先用的递归来做的：

int jumpFloor2(int number) {
        if (number < 0) return 0;
        if (number < 2) return 1;
        return jumpFloor(number-1) + jumpFloor(number-2);
    }

耗时如下：

然后用的DP做的：

int jumpFloor2(int number) {
        if (number < 0) return 0;
        if (number < 2) return 1;
        int jump2 = 1;
        int jump1 = 1;
        for (int i=2; i<=number; i++) {
            int tmp = jump2 + jump1;
            jump2 = jump1;
            jump1 = tmp;
        }
        return jump1;
    }