猴子上山—迭代方法（图文解析）

题目描述

一只猴子正在攀登一座高度不超过30级的山丘，其攀爬过程中每次可选择向上跳跃1级或3级，试计算该猴子完成登山任务共有多少种不同的路径方式。

样例输入解析

30

样例输出

58425

解题思路分析

1. 首先分析f[k]的递推规律
   假设n=30，当最后一次跳跃抵达第30级台阶时，即完成上山过程，此时共有f[30]种不同的攀登方式；在到达第30级台阶之前，可能处于哪一级呢？第一种情况是处于第29级（只需再跳1级即可抵达），对应的爬法数量为f[29]；第二种情况是处于第27级（只需再跳3级即可抵达），对应的爬法数量为f[27]；因此可以得出：
   f[30]=f[29]+f[27]
   由此类推，可以得到普遍适用的递推公式：
   f[k]=f[k-1]+f[k-3] （k>3）

2. 明确初始条件
   当k=1时，有f[1]=1；即仅有一种方式：1步
   当k=2时，有f[2]=1；即两种方式：1+1
   当k=3时，有f[3]=2；即三种方式：1+1+1 或者直接跳3步

3. 执行递推计算
   依据上述递推公式以及初始条件设定，通过构建一个循环结构并依次进行计算，即可求得任意n对应的f[n]值。

![在这里插入图片描述](https://ad.itadn.com/c/weblog/blog-img/i