题目

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

示例：

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
复制代码

分析

本题可以算是动态规划题型的基础，基本其它复杂的题目都是由它演变而来，需要牢牢掌握

动态规划的题目我们同样有相应的解题步骤

• 定义dp数组来表示我们求解的结果

dp = [] ，dp[n] 表示 n 之前两数相加之和

• 写出状态转移方程

将状态转移方程用dp数组表示

dp(N) =dp(N - 1) + dp(N - 2)

进行初始化

dp[0] = 0, dp[1] = 1

使用迭代计算出结果并返回

实现

function fib(n: number): number {
    let dp = []
    dp[0] = 0
    dp[1] = 1
    let i = 2
    while(i <= n) {
        dp[i] = (dp[i - 1] + dp[i - 2])%1000000007
        i ++
    }
    return dp[n]
};
复制代码

题目

剑指 Offer 10- II. 青蛙跳台阶问题

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

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例：

输入：n = 2
输出：2
复制代码

分析

台阶问题也是动态规划的经典题目，将复杂问题转化为简单模型来进行求解

还是按照我们求解动态规划题目的套路来

• 定义好 dp 数组

dp[n] 表示青蛙跳上 n 级台阶有几种方法

• 用dp数组写出状态转移方程，第n阶的跳法可以由第n-1阶和第n-2阶的跳法相加得来，即

dp[n] = dp[n-1] + dp[n-2]

• 初始化 dp 数组

dp[0] = 1；dp[1] = 1; dp[2] = 2; dp[3] = dp[1] + dp[2] = 3

• 迭代计算结果并返回

实现

function numWays(n: number): number {
    let dp: number[] = []
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    let i: number = 3
    while(i <= n) {
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
        i++
    }
    return dp[n]
};