821. 跳台阶

821. 跳台阶

⭐️难度：简单
⭐️类型：递归

📖题目：题目链接

🌟思路：
问题太复杂，没办法全局考虑，考虑分治法，
逐渐降低复杂度，把大问题分解成若干相似小问题（小问题能够直接解决）。

题中：
①最后一步一定走一级或二级，问题倒退成 要解决的问题是走n-1级和n-2级有多少种方案；
但问题到这里还是不简单，继续倒推：
②假设剩下台阶数是n，倒数第二步一定走一级或二级，问题倒退成 要解决的问题是走n-1级和n-2级有多少种方案；
… …
③不难发现，每一次分解，问题的解决思路是一致的，可以用同样的式子表达出来，最后问题会退化成走012个台阶有几种方案；
④显而易见，口算就能知道，走01个台阶只有 1 种方案，走2个台阶有 2种方案（走一级再走一级 和 一次走两级）。

📚题解：
找到方法后，代码其实并不复杂：

#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<string.h>#include<vector>// vector不需要.h#include<list>#include<set>// // 可以用 set 和 multiset#include<unordered_set>// 可以用 unordered_set 和 unordered_multiset#include<map>// 可以用 map 和 multimap#include<unordered_map>// 可以用 unordered_map 和 unordered_multimap#include<algorithm>#include<string>#include<iostream>#include<queue>#include<stack>usingnamespacestd;intfangan(intn){// 重点：找到递归出口if(n==0||n==1){return1;}if(n==2){return2;}returnfangan(n-1)+fangan(n-2);}intmain(){intn;scanf("%d",&n);intres=fangan(n);printf("%d",res);return0;}