经典算法 - 斐波那契数列
题目
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思路
斐波那契数列,其实就是靠着前一个状态和前二个状态,推出了下一个状态
public class Solution {
public int JumpFloor(int target) {
if (target <= 2) {
return target;
}
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= target; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target];
}
}
此时,可以发现,空间是可以压缩的,因为一个状态,只跟前两个状态有关系,之前的都不需要了
public class Solution {
public int JumpFloor(int target) {
if (target <= 2) {
return target;
}
// 前一个状态 & 前二个状态
int p1 = 1;
int p2 = 2;
int result = 0;
for (int i = 3; i <= target; i++) {
// 求结果
result = p1 + p2;
// 状态分别后移
p1 = p2;
p2 = result;
}
return result;
}
}
总结
有很多种变种问法
- 比如一次性可以跳1级,3级的,怎么算?若一次性可以跳 N 级呢?(牛客网 - 变态跳台阶)
- 例如,抽奖,一次抽一次,结果可以为抽到一元或二元,要凑 x 元,有多少种凑法?(老虎集团 2020 春招笔试第二场)
- 例如,母牛每年都会生 1 头小母牛,并且永远不会死。第一年有 1 只小母牛,从第二年开始,母牛开始生小母牛。每只小母牛 3 年后又可以生小母牛。求 N 年后牛的数量(奶牛生产问题)
这次老虎证券笔试第二道就是抽奖题,而之前在奇安信笔试的第二道也是兔子问题,其实也都是这类问题
老虎的笔试一看还以为是数学题,吓了一跳,要没时间了才发现是斐波那契数列。。。写完后也不知道对不对,在这里再刷一遍,验证看起来是对的