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

本文主要是介绍【LeetCode】70. Climbing Stairs【牛客网】变态跳台阶，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天在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），我们可以套用斐波那契通项公式直接求解

$$a(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]$$

/*爬楼梯--通项公式*/
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=0if number==1:jump=jump+1else:jump=jump+2*self.jumpFloorII(number-1)return jump

这篇关于【LeetCode】70. Climbing Stairs【牛客网】变态跳台阶的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---