数据结构与算法练习-递归数据结构

青蛙跳一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法
代码

public static int getStep(int n) { if (n == 0) { return 0; } // 步数为1 有1种跳法 if (n == 1) { return 1; } // 步数为2有2种跳法 if (n == 2) { return 2; } // 步数为3 可以分解为步数1+2 // ... return getStep(n - 1) + getStep(n - 2); }

变态青蛙跳一只青蛙一次可以跳上1级台阶，也可以跳上2级，…….也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
分析
对于n阶阶梯
f(n) =f(n-1)+f(n-2)+….+f(n-n)
同时
f(n-1)=f(n-2)+f(n-3)+….+f(n-n)
那么
f(n)=f(n-1)+f(n-1)=2*f(n-1)
表达

// 变态跳阶梯 public static int getStepUp(int n) { if (n == 0) { return 0; } // 步数为1 有1种跳法 if (n == 1) { return 1; } // 步数为2有2种跳法 if (n == 2) { return 2; } // 步数为3 可以分解为步数1+2 // ... return 2 * getStepUp(n - 1); }

矩形覆盖 【数据结构与算法练习-递归】描述
我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
分析：
应为可以横着放或竖着放，多以f(n)可以是2*(n-1)的矩形加一个竖着放的2*1的矩形或2*(n-2)的矩形加2横着放的，即f(n)=f(n-1)+f(n-2)
代码
和青蛙跳问题一致