华为OD机试C卷-- 猴子爬山（Java & JS & Python）

获取题库不需要订阅专栏，可直接私信我进入CSDN领军人物top1博主的华为OD交流圈观看完整题库、最新面试实况、考试报告等内容以及大佬一对一答疑。
题目描述
一天一只顽猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：
每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的跳跃方式？

输入描述
输入只有一个整数N（0<N<=50）此阶梯有多少个台阶。

输出描述
输出有多少种跳跃方式（解决方案数）。

题目解析
这个问题是一个经典的动态规划问题，可以使用递推或者动态规划表的方式来解决。由于猴子每次只能跳1步或3步，我们可以定义一个状态转移方程来计算到达每个台阶的方法数。设dp[n]表示到达第n个台阶的跳跃方法数，那么有：

• 当n=1时，只有1种方法（跳1步）到达，即dp[1]=1；
• 当n=2时，无法直接到达（因为不能跳2步），所以dp[2]=0（这里实际上可以
• 根据题目理解调整，如果允许站在原地也算一种状态，则dp[2]=1，但根据常规理解和大多数解法，我们设定为0）；
• 当n=3时，可以一步跳到或从第一个台阶跳两次到达，共有2种方法，即dp[3]=2；
• 对于n>3的情况，到达第n个台阶的方法数等于到达第n-1