71.md

跳台阶扩展问题

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

进阶：空间复杂度 O(1)， 时间复杂度 O(1)

示例

输入：3 返回值：4

思路

与 69 题有什么不同

• 69 题 [先后次序不同算不同的结果], 本题不是

头脑风暴

• 设 f[i] 表示 当前跳道第 i 个台阶的方法数。那么f[n]就是所求答案。
• 假设现在已经跳到了第 n 个台阶，那么前一步可以从哪些台阶到达呢？
• 如果上一步跳 1 步到达第 n 个台阶，说明上一步在第 n-1 个台阶。已知跳到第n-1个台阶的方法数为f[n-1]
• 如果上一步跳 2 步到达第 n 个台阶，说明上一步在第 n-2 个台阶。已知跳到第n-2个台阶的方法数为f[n-2]
• 如果上一步跳 n 步到达第 n 个台阶，说明上一步在第 0 个台阶。
• 已知跳到第0个台阶的方法数为f[0]
• 那么总的方法数就是所有可能的和。也就是f[n] = f[n-1] + f[n-2] + ... + f[0]
• 显然初始条件f[0] = f[1] = 1
• 所以我们就可以先求f[2]，然后f[3]...f[n-1]， 最后f[n]

更近一步

• f[n] = f[n-1] + f[n-2] + ... + f[0]
• 那么f[n-1] 为多少呢？
• f[n-1] = f[n-2] + f[n-3] + ... + f[0]
• 所以一合并，f[n] = 2*f[n-1]，初始条件f[0] = f[1] = 1

实现

func jumpFloorII(number int) int {
	if number <= 1 {
		return 1
	}
	var a = 1
	var b = 0
	for i := 2; i <= number; i++ {
        // b = a * 2 
		b = a << 1 // 跟上边是一回事儿
		a = b
	}
	return b
}