剑指offer-跳台阶

梦里梦外; 2022-02-17 05:39 173阅读 0赞

##### 题目描述 #####

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

##### 实现思想 #####

对于本题，可以从后往前推，最后一次有两种跳法，当最后一次跳了1阶台阶的时候和最后一次跳了两阶台阶的时候。  
a.假定最后一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1);  
b.假定最后一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)  
c.由a、b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2)  
d.然后通过实际的情况可以得出：总的台阶数为一阶的时候 f(1) = 1 ，台阶数只有两阶的时候有 f(2) = 2  
e.可以发现最终得出的是一个上一题的斐波那契数列

##### 代码实现 #####

因为前面一道题算斐波那契数列的时候用了递归的办法和非递归的办法，这里我们用动态规划的办法实现这道题

class Solution {
    public:
        int jumpFloor(int number) {
            if(number <= 0) return 0;
            if(number == 1) return 1;
            if(number == 2) return 2;
            int first = 1, second = 2, third = 0;
            for (int i = 3; i <= number; i++) {
                third = first + second;
                first = second;
                second = third;
            }
            return third;
        }
    };

##### 运行截图 #####

因为题目简单，所以没有在编译器上运行，故没有运行截图。

##### 总结 #####

**动态规划的思想：**  
大事化小，小事化了。把一个复杂的问题分阶段进行简化，逐步化简成简单的问题。  
**问题建模：**  
1、 根据问题，找到【最优子结构】。  
把原问题从大化小的第一步，找到比当前问题要小一号的最好的结果，而一般情况下当前问题可以由最优子结构进行表示。如f(n-1) 和 f(n-2)  
2、确定问题的【边界】。  
根据上述的最优子结构，一步一步从大化小，最终可以得到最小的，可以一眼看出答案的最优子结构，也就是边界。如 f(1) = 1， f(2) = 2  
3、通过上述两步，通过分析最优子结构与最终问题之间的关系，我们可以得到【状态转移方程】。如f(n) = f(n-1) + f(n-2)