变态跳台阶动态规划和递归解法

一、题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
示例1
输入
3
返回值
4
二、思路
这道题的思路是典型的动态规化的思路，先从上往下思考问题，剖析问题，然后再从下往上解决问题。因为如果一开始就从下往上思考问题，会有很多中情况，比如从第0个台阶开始向第n个台阶跳跃，有无数种可能性。如果从上开始思考，站在第N个台阶向下思考，跳到n个台阶有f(n)种方法，n-1个台阶有f(n-1)种方法，然后再思考f(n)和f(n-1）之间有何关系，仔细推导，可以得知f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(1)+f(0),这是一个关系式，我们可以知道f(0)=f(1)=1，因此，可以从下往上把f(n)给算出来，这就是动态规划。
三、动态规划的代码

class Solution {
public:
    int jumpFloorII(int number) {
         vector<int> f(number+1,0);//vector数组功能很强大，可以直接用变量来定义数组的大小。因为vector是一个动态数组。
        f[0]=f[1]=1;
        for(int i=2;i<=number;i++){
            for(int j=0;j<i;j++){
                f[i]+=f[j];
            }
        }
        return f[number];
    }
};

四、递归的方法
仔细观察关系式f(n)=f(n-1)+f(n-2)+f(n-3)+…+f(1)+f(0），f(n-1)=f(n-2)+f(n-3)+…+f(1)+f(0）,因此f(n)=2*f(n-1),这就找到了f(n)与f(n-1）之间的关系式，可以用递归方法。

class Solution {
public:
    int jumpFloorII(int number) {
         if(number==1)
             return number;
        else
            return 2*jumpFloorII(number-1);
    }
};

五、因为本题考察的思想是贪心算法，我们有想出来贪心策略应该如何做，动态规划和贪心还是有区别的，虽然有的人认为贪心是动规的一种。

最后

以上就是甜甜眼神为你收集整理的变态跳台阶动态规划和递归解法的全部内容，希望文章能够帮你解决变态跳台阶动态规划和递归解法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。