题目描述:
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路:
这是一道经典的递推题目，你可以想如果青蛙当前在第n级台阶上，那它上一步是在哪里呢？
显然，由于它可以跳1级台阶或者2级台阶，所以 它上一步必定在第n-1,或者第n-2级台阶，也就是说 它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。
设跳上
级台阶有 种跳法，则它跳上n级的台阶有 种跳法。
然后，我们又思考初始（
）的情况，跳上1级台阶只有1种跳法，跳上2级台阶有2种跳法，最终我们得到如下的递推式：
方法一：
public class Solution {
public int JumpFloor(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
return JumpFloor(n - 1) + JumpFloor(n - 2);
}
}
方法二：
public class Solution {
public int JumpFloor(int target) {
int a = 1, b = 1;
for (int i = 1; i < target; i++) {
a = a + b;
b = a - b;
}
return a;
}
}
Original: https://www.cnblogs.com/lkylin/p/13489551.html
Author: 手下留情
Title: 剑指Offer:跳台阶(10.3)
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/564839/
转载文章受原作者版权保护。转载请注明原作者出处！