面试题10- II. 青蛙跳台阶问题

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

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例1


输入:n = 2
输出:2


示例2


输入:n = 7
输出:21

提示

0 <= n <= 100

解题过程

经典的动态规划问题

这里只讲动态规划解法

  1. 列出转移方程 f[n] = f[n-1] + f[n -2]
  2. 写出初始条件 f[0] = 1,f[1] = 1
  3. 找到边界,最大为n,最小0

问题

因为这里算出的值会出现溢出,因此需要进行取模运算。

为什么是最每次取模了,这里列出个式子,

sum = a + b + c sum % d = a % d + b % d + c % d

因此可以对每次的和进行取模,结果是不会改变的,也避免相加过程中出现溢出的情况。


func numWays(n int) int {
	f := make([]int, 2, 2)
	mod := 1000000007
	f[0] = 1
	f[1] = 1
	if n < 2 {
		return f[n]
	}
	var sum int
	for i := 2; i <= n; i++ {
		sum = (f[i-1] + f[i-2]) % mod
		f = append(f, sum)
	}
	return f[n]
}