写在前

百度百科：斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……这个数列从第三项开始，每一项都等于前两项之和。裴波那契数列最具有和谐之美的地方是，越往后，相邻两项的比值会无限趋向于黄金比1:0.618

斐波纳契螺旋线

在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。详情百度百科。

而动态规划，就要有一个数组来记录状态！

1.斐波那契数（509-易）

题目描述：斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

思路：本题题目描述已经给出状态转移方程，直接写代码，然后进行空间复杂度优化。注意：初始值dp[0] = 0。

代码：动态规划

public int fib(int n) {
    if (n == 0) return 0;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

空间优化：注意，先更新前一个变量，避免覆盖。

public int fib(int n) {
    if (n == 0) return 0;
    int pre1 = 0, pre2 = 1;
    for (int i = 2; i <= n; ++i) {
        int cur = pre1 + pre2;
        pre1 = pre2;
        pre2 = cur;
    }
    return pre2;
}

2.爬楼梯（70-易）

题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。

示例：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

思路：本题先写出暴力解法，然后改写为动态规划，最后进行空间优化，其中，dp[i]代表走到第i阶楼梯的方法数。

代码1：递归暴力求解：F(n) = F(n - 1) + F(n - 2) （n > 2）

public int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

ps：Leetcode测试超时！

代码2：动态规划

public int climbStairs(int n) {
    if (n == 1) return 1;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

空间优化：O(1)

public int climbStairs(int n) {
    if (n == 1) return 1;
    int pre1 = 1, pre2 = 2;
    for (int i = 3; i <= n; ++i) {
        int cur = pre1 + pre2;
        pre1 = pre2;
        pre2 = cur;
    }
    return pre2;
}

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

class Solution {
    public int numWays(int n) {
        // 注意判断特例！！！
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }

    public int numWays(int n) {
        // 空间压缩
        if (n == 0 || n == 1) {
            return 1;
        }
        int pre = 1, cur = 1;

        for (int i = 2; i <= n; i++) {
            int tmp = (pre + cur) % 1000000007;
            pre = cur;
            cur = tmp;
        }
        return cur;
    }
}

3.最小花费爬楼梯（746-易）

题目描述：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。支付相应的体力值。你可以爬一个阶梯或者两个阶梯，求达到顶部的最小花费，在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。。

示例：

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 
输出：6 
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

思路：dp[i]：到达第i个台阶所花费的最少体力。**由于题目要求每爬上一个楼梯都要支付对应的体力值，才能进行下一步。并且上一步花费的体力值最小（走一步和两步），注意：最后一步不需要花费。

• 状态转移方程式：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]。

代码：动态规划

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int[] dp = new int[n];
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < n; ++i) {
        dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
    }
    // 最后一步不需要花费，取倒数第1步和倒数第2步的最小值
    return Math.min(dp[n - 1], dp[n - 2]);
}

空间优化：O(1)

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int pre1 = cost[0], pre2 = cost[1];
    for (int i = 2; i < n; ++i) {
        int cur = Math.min(pre1, pre2) + cost[i];
        pre1 = pre2;
        pre2 = cur;
    }
    return Math.min(pre1, pre2);
}

4.信件错排（补充Leetcode-634）

题目描述：有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量。

思路：本题显然是一个动态规划问题，定义dp数组存储错误方式的数量，dp[i]表示有i封信，i个信箱错误方式。事实上，对于信件 i 来说，信箱 i 是它的“专属信箱”，每个信件都不能放入自己的专属信箱。

状态转移方程：对于第N封信而言，假设其装在了第 K 个信箱中，对于第 K 封信，有两种情况：

（1）信件 K 装在信箱 N 中

image.png

这时，已经完成K和N两个信封，只关注剩下 N-2 对信件和信箱，有 dp[N-2] 种错误装信方法；K 的取值范围： 1~N-1 ，因此共有 (N-1)*dp[N-2] 种错误装信方法。

（2）信件 K 未被装在信箱 N 中

image.png

假设每个信封都有自己的专属信箱，N的专属信箱为K，那么可以认为K的专属信箱为N。因为本情况下，信件 K 不能放入自己的专属信箱 N 。所以可以理解成求 N-1 封信件和 N-1 个信箱（除去信件 N）之间的错排数量问题。即求 dp[N-1]。同时，K 的取值范围： 1~N-1 ，因此共有 (N-1)*dp[N-1] 种错误装信方法。

• 状态转移方程：dp[i] = (i-1)*dp[i-2] + (i-1)*dp[i-1]

代码：动态规划

public int MailMisalignment(int n){
    if(n == 0 || n == 1) return 0;
    int[] dp = new int[n];
    dp[0] = 0;
    dp[1] = 1;
    for(int i = 2; i < n; ++i){
        dp[i] = (i - 1) * (dp[i-2] + dp[i-1]);
    }
    return dp[n - 1];
}

5.母牛生产（程序员代码面试指南-P181）

题目描述：假设农场中成熟的母牛每年都会生 1 头小母牛，并且永远不会死。第一年有 1 只小母牛，从第二年开始，母牛开始生小母牛。每只小母牛 3 年之后成熟又可以生小母牛。给定整数 N，求 N 年后牛的数量。

思路：dp数组存储每年成熟小母女的数量。因为只有成熟的母女才会继续生产牛。例：1，2，3，4，6 ... ... 即第N年后牛的数量等于第N - 1年牛的数量，加上第N - 3年成熟小母牛下的小母牛(3年成熟)。

• 状态转移方程：dp[i] = dp[i - 1] + dp[i - 3], n > 3

代码：动态规划

public int cow(int n) {
    if (i < 4) return n;
    int[] dp = new int[n + 1];
    // 起始条件
    for (int i = 0; i < 4; ++i) {
        dp[i] = i;
    }
    // 从第4年才满足状态转移方程
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 3];
    }
    return dp[n];
}