题目
- 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法
- 21长方形方格填充2n的方格有多少种填法
题解
此类问题都是斐波那契数列变种、应用题。通常解法比较简单，递归、循环
- 递归：
int[] dp;
private int resolveDGPrivate(int n) {
if (n == 0 || n == 1) return 1;
if (dp[n] > 0) return dp[n];
int n1 = resolveDGPrivate(n - 1);
int n2 = resolveDGPrivate(n - 2);
dp[n - 1] = n1;
dp[n - 2] = n2;
return n1 + n2;
}
public int resolveDG(int n){
dp=new int[n+1];
return resolveDGPrivate(n);
}
- 循环
public int resolve(int n) {
if (n == 0 || n == 1) return 1;
int prepre = 1;
int pre = 1;
int sum = 0;
for (int i = 1; i < n; i++) {
sum = prepre + pre;
prepre = pre;
pre = sum;
}
return sum;
}
通常来说循环更实用，递归代码更加简洁。
源码: 剑指offer4J
