【LeetCode】70. Climbing Stairs【牛客网】变态跳台阶1、跳台阶2、变态跳台阶

今天在LeetCode做到一个动态规划的题，之前在牛客网做过一道“变态跳台阶”的题，猛一看还以为是一个意思，牛客网那边能AC，LeetCode这边却不能AC，很奇怪，其实题目有细微的差别，

这两题难道不是一个意思吗？

1、跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种方法？
与LeetCode Problem No.70 Climbing Stairs相同，属于动态规划问题，可以使用递归求解。

递归法

/*爬楼梯*/
int climbStairs(int n) 
{
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

但递归法求解的过程中会多次处理子问题的解，当输入值较大时导致效率大打折扣，这题迭代法效率太慢将导致超时，我们可以将递归转化为迭代法

迭代法

迭代法就是用空间换时间，先求解子问题并存起来，最后直接索引原问题的解

    /*爬楼梯--迭代*/
    int climbStairs1(int n)
    {
        int steps[999];
        steps[0] = 0;
        steps[1] = 1;
        steps[2] = 2;
        if (n == 1) return steps[1];
        if (n == 2) return steps[2];
        else
        {
            for (int i = 3; i < 999; i++)
            {
                steps[i] = steps[i - 1] + steps[i - 2];
            }
        }
        return steps[n];
    }

公式法

另外这题与菲波那切数列完全一致（除了n=0），我们可以套用斐波那契通项公式直接求解

/*爬楼梯--通项公式*/
int climbStairs2(int n)
{
    n++;
    double root5 = sqrt(5);
    //double root5 = pow(5, 0.5);
    double result = 1 / root5*(pow((1 + root5) / 2, n) - pow((1 - root5) / 2, n));
    return (int)(result);
}

2、变态跳台阶

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

因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以f(n)=f(n-1)+f(n-2)+…+f(1)
因为f(n-1)=f(n-2)+f(n-3)+…+f(1)
所以f(n)=2*f(n-1)

def jumpFloorII(self, number):
        int jump=0
        if number==1:
            jump=jump+1
        else:
            jump=jump+2*self.jumpFloorII(number-1)
        return jump

最后

以上就是优美冰淇淋为你收集整理的【LeetCode】70. Climbing Stairs【牛客网】变态跳台阶1、跳台阶2、变态跳台阶的全部内容，希望文章能够帮你解决【LeetCode】70. Climbing Stairs【牛客网】变态跳台阶1、跳台阶2、变态跳台阶所遇到的程序开发问题。

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