写在前
百度百科：斐波那契数列（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]; }
