青蛙跳台阶题目青蛙一次只能跳 1级 或 2级求跳到第 n 级台阶一共有多少种跳法。核心逻辑关键逆向思考想站上第 n 级台阶最后一步只存在两种可能性没有别的情况最后一跳跳 1级说明在这一跳之前青蛙已经站在第 n-1 级。前面所有到达 n-1 的走法接上这一下跳1级就都是到n阶的合法方案。方案数量 到达 n-1 的方案数。最后一跳跳 2级说明在这一跳之前青蛙已经站在第 n-2 级。前面所有到达 n-2 的走法接上这一下跳2级就都是到n阶的合法方案。方案数量 到达 n-2 的方案数。所有方案不会重叠、不会漏掉。所以递推式f(n)f(n-1)f(n-2)边界条件基础情况不能靠递推算直接定义f(1)1只有1级台阶只能跳1次1级1种方案f(2)2两种①11 ②直接跳2级2种方案重点递推式子长得一样但初始值不一样所以数列本身和标准斐波那契不是一回事。标准斐波那契F(1)1F(2)1青蛙跳f(1)1f(2)2。两种实现思路递归cint f(int n){if(n 1) return 1;if(n 2) return 2;return f(n-1)f(n-2);}缺点不断重复计算相同的f(k)n大之后效率极低。迭代循环推荐从底层从小往大一步步算只保存最近两个值节省空间cint frog(int n){if(n 1) return 1;if(n 2) return 2;int b 1; // f(n-2)int a 2; // f(n-1)int c;for(int i 3; i n; i){c a b;b a;a c;}return a;}扩展变种青蛙可以跳1~n任意阶逆向推导到n阶最后一步可以从 n-1 / n-2 / … /0 直接跳上来f(n)f(n-1)f(n-2)…f(1)到n阶的全部走法 到n-1阶所有走法 到n-2阶所有走法边界单独定死不要直接套用斐波那契的初始条件。如果每次跳的是偶数格则n为奇数是都为0。但是每次跳奇数格就没限制。最重要就是看原理公式和找到特殊项