寫在前
百度百科：斐波那契數(shù)列（Fibonacci sequence）彻亲，又稱黃金分割數(shù)列太雨，因數(shù)學家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”镶奉，指的是這樣一個數(shù)列：0是鬼、1饥追、1、2、3揭厚、5却特、8、13筛圆、21裂明、34、……這個數(shù)列從第三項開始太援，每一項都等于前兩項之和闽晦。裴波那契數(shù)列最具有和諧之美的地方是，越往后提岔，相鄰兩項的比值會無限趨向于黃金比1:0.618
斐波納契螺旋線：
在現(xiàn)代物理、準晶體結構碱蒙、化學等領域荠瘪，斐波納契數(shù)列都有直接的應用。詳情百度百科赛惩。
而動態(tài)規(guī)劃哀墓，就要有一個數(shù)組來記錄狀態(tài)！
1.斐波那契數(shù)（509-易）
題目描述：斐波那契數(shù)喷兼，通常用 F(n) 表示篮绰，形成的序列稱為 斐波那契數(shù)列 。該數(shù)列由 0 和 1 開始季惯，后面的每一項數(shù)字都是前面兩項數(shù)字的和吠各。也就是：
F(0) = 0，F(xiàn)(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
思路：本題題目描述已經(jīng)給出狀態(tài)轉移方程琳状，直接寫代碼，然后進行空間復雜度優(yōu)化盒齿。注意：初始值dp[0] = 0念逞。
代碼：動態(tài)規(guī)劃
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];
}
空間優(yōu)化：注意，先更新前一個變量边翁，避免覆蓋翎承。
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 階
思路：本題先寫出暴力解法，然后改寫為動態(tài)規(guī)劃甸各，最后進行空間優(yōu)化垛贤，其中，dp[i]代表走到第i階樓梯的方法數(shù)趣倾。
代碼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：動態(tài)規(guī)劃
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];
}
空間優(yōu)化：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-易）
題目描述：數(shù)組的每個下標作為一個階梯，第 i 個階梯對應著一個非負數(shù)的體力花費值 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] 開始衣洁，逐個經(jīng)過那些 1 ，跳過 cost[3] 抖仅，一共花費 6 坊夫。
思路：dp[i]：到達第i個臺階所花費的最少體力。**由于題目要求每爬上一個樓梯都要支付對應的體力值撤卢，才能進行下一步环凿。并且上一步花費的體力值最小（走一步和兩步）放吩，注意：最后一步不需要花費智听。
- 狀態(tài)轉移方程式：
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]。
代碼：動態(tài)規(guī)劃
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];
}
// 最后一步不需要花費渡紫，取倒數(shù)第1步和倒數(shù)第2步的最小值
return Math.min(dp[n - 1], dp[n - 2]);
}
空間優(yōu)化：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 個 信 和 信封到推，它們被打亂，求錯誤裝信方式的數(shù)量惕澎。
思路：本題顯然是一個動態(tài)規(guī)劃問題莉测，定義dp數(shù)組存儲錯誤方式的數(shù)量，dp[i]表示有i封信唧喉，i個信箱錯誤方式捣卤。事實上忍抽，對于信件 i 來說，信箱 i 是它的“專屬信箱”腌零，每個信件都不能放入自己的專屬信箱梯找。
狀態(tài)轉移方程：對于第N封信而言，假設其裝在了第 K 個信箱中益涧，對于第 K 封信锈锤，有兩種情況：
（1）信件 K 裝在信箱 N 中
這時，已經(jīng)完成K和N兩個信封闲询，只關注剩下 N-2 對信件和信箱久免，有 dp[N-2] 種錯誤裝信方法；K 的取值范圍： 1~N-1 扭弧，因此共有 (N-1)*dp[N-2] 種錯誤裝信方法阎姥。
（2）信件 K 未被裝在信箱 N 中
假設每個信封都有自己的專屬信箱，N的專屬信箱為K鸽捻，那么可以認為K的專屬信箱為N呼巴。因為本情況下，信件 K 不能放入自己的專屬信箱 N 御蒲。所以可以理解成求 N-1 封信件和 N-1 個信箱（除去信件 N）之間的錯排數(shù)量問題衣赶。即求 dp[N-1]。同時厚满，K 的取值范圍： 1~N-1 府瞄，因此共有 (N-1)*dp[N-1] 種錯誤裝信方法。
- 狀態(tài)轉移方程：
dp[i] = (i-1)*dp[i-2] + (i-1)*dp[i-1]
代碼：動態(tài)規(guī)劃
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.母牛生產(chǎn)（程序員代碼面試指南-P181）
題目描述：假設農(nóng)場中成熟的母牛每年都會生 1 頭小母牛碘箍，并且永遠不會死遵馆。第一年有 1 只小母牛，從第二年開始丰榴，母牛開始生小母牛货邓。每只小母牛 3 年之后成熟又可以生小母牛。給定整數(shù) N四濒，求 N 年后牛的數(shù)量换况。
思路：dp數(shù)組存儲每年成熟小母女的數(shù)量。因為只有成熟的母女才會繼續(xù)生產(chǎn)牛峻黍。例：1复隆，2拨匆，3姆涩，4，6 ... ... 即第N年后牛的數(shù)量等于第N - 1年牛的數(shù)量惭每，加上第N - 3年成熟小母牛下的小母牛(3年成熟)骨饿。
- 狀態(tài)轉移方程：
dp[i] = dp[i - 1] + dp[i - 3], n > 3
代碼：動態(tài)規(guī)劃
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年才滿足狀態(tài)轉移方程
for (int i = 4; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 3];
}
return dp[n];
}
