動(dòng)態(tài)規(guī)劃
寫在前面
沒(méi)思路的時(shí)候就把樹畫出來(lái)布卡，這會(huì)事半功倍
概述
我們首先明確一點(diǎn)雨让，動(dòng)態(tài)規(guī)劃問(wèn)題的一般形式就是求最大值或者最小值。
其核心就是窮舉羽利。因?yàn)榍笞钪悼隙ㄒ獙⑵淙康目赡芏剂谐鰜?lái)宫患，這才找的出最值。
動(dòng)態(tài)規(guī)劃適合的窮舉具有重疊子問(wèn)題的特征，如果暴力窮舉娃闲，效率回極其低下虚汛，所以需要備忘錄或則DB table來(lái)優(yōu)化窮舉過(guò)程，避免不必要的計(jì)算皇帮。
動(dòng)態(tài)規(guī)劃問(wèn)題一定具備最優(yōu)子結(jié)構(gòu)性質(zhì)卷哩，這樣才可以通過(guò)子問(wèn)題得到原問(wèn)題的解。
動(dòng)態(tài)規(guī)劃問(wèn)題的核心是就是窮舉出最值属拾，但是問(wèn)題可以千變?nèi)f化将谊，窮舉出所有可行解并不是 容易的事情，只有列出正確的動(dòng)態(tài)轉(zhuǎn)移方程渐白，才可以正確的窮舉尊浓。寫出動(dòng)態(tài)轉(zhuǎn)移方程也是最難的。
**
寫出動(dòng)態(tài)轉(zhuǎn)移方程的核心要義
步驟
1.這個(gè)問(wèn)題最簡(jiǎn)單的情況（basecase）是什么
2.這個(gè)問(wèn)題有什么狀態(tài)
3.每個(gè)狀態(tài)可以做什么纯衍，可以做出什么選擇使得狀態(tài)發(fā)送變化
4.如何定義dp數(shù)組/函數(shù)的含義來(lái)表現(xiàn)“狀態(tài)”和選擇
基本框架
#初始化basecase
db[][]..=base case
#進(jìn)行狀態(tài)轉(zhuǎn)移
for 狀態(tài)1 in 狀態(tài)2的所有取值
for 狀態(tài)1 in 狀態(tài)2的所有取值
斐波那契數(shù)入門動(dòng)態(tài)規(guī)劃
Leetcode鏈接509 斐波那契數(shù)：https://leetcode-cn.com/problems/fibonacci-number/
題目描述
斐波那契數(shù)栋齿，通常用 F(n) 表示，形成的序列稱為 斐波那契數(shù)列 襟诸。該數(shù)列由 0 和 1 開始瓦堵，后面的每一項(xiàng)數(shù)字都是前面兩項(xiàng)數(shù)字的和。也就是：
F(0) = 0歌亲，F(xiàn)(1) = 1
F(n) = F(n - 1) + F(n - 2)菇用，其中 n > 1
給你 n ，請(qǐng)計(jì)算 F(n) 陷揪。
示例 1：
輸入：2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
輸入：3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
輸入：4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3
1.解法1惋鸥，暴力遞歸窮舉
代碼
public int fib(int n) {
if (n==0){
return 0;
}
if (n==1||n==2){
return 1;
}
return fib(n-1)+fib(n-2);
}
注意：但凡遇到遞歸的問(wèn)題都應(yīng)該畫出遞歸樹，這對(duì)分析算法的復(fù)雜度鹅龄，尋找算法低效性的原因都有巨大的幫助
遞歸樹圖解
從遞歸樹中我們可以看到這存在大量的重復(fù)的運(yùn)算揩慕，這是沒(méi)意義的運(yùn)算而且十分耗時(shí)。
要計(jì)算fib（5）就必須計(jì)算fib（4）和fib（3）
要計(jì)算fib（4）就必須計(jì)算fib（3）和fib（2）
如果fib（4）中已經(jīng)計(jì)算過(guò)fib（3）那么fib（5）中就不必重復(fù)計(jì)算fib（3）了扮休，這時(shí)候就需要引入DP table 或則備忘錄，通過(guò)查表的方式來(lái)判斷該值有沒(méi)有計(jì)算過(guò)玷坠，有沒(méi)有重復(fù)計(jì)算
時(shí)間復(fù)雜度分析
二叉樹的節(jié)點(diǎn)個(gè)數(shù)為指數(shù)級(jí)別劲藐，所求子問(wèn)題的個(gè)數(shù)為O（2^n）
解決一個(gè)子問(wèn)題的時(shí)間為O（1），因?yàn)橹瞪婕暗揭粋€(gè)加法運(yùn)算
故時(shí)間復(fù)雜度為 O(2^n)
消耗的內(nèi)存與時(shí)間情況
2.解法二聘芜，備忘錄解法
在解法1中我們也介紹了暴力解法中存在的問(wèn)題兄渺，及其問(wèn)題存在的原因，那么在解法二中我們就通過(guò)加上備忘錄的方式挂谍，來(lái)避免重復(fù)計(jì)算，這樣可以大大提高解題的效率
代碼
class Solution {
int[] DpTable;
public int fib(int n){
DpTable=new int[n+1];
return fib2(n);
}
public int fib2(int n) {
/*結(jié)束遞歸的條件*/
if (n==0){
return 0;
}
if (n==1||n==2){
return 1;
}
if (DpTable[n]!=0){
return DpTable[n];
}
DpTable[n]=fib2(n-1)+fib2(n-2);
return DpTable[n];
}
}
消耗的內(nèi)存與時(shí)間情況
3.解法3 dp數(shù)組的迭代解法
我們可以把備忘錄獨(dú)立出來(lái)成為一張表口叙，就叫做DB table 在這張表上自底向上推算
代碼
class Solution {
public int fib(int n) {
if (n==0){
return 0;
}
if (n==1||n==2){
return 1;
}
int[] arr = new int[n+1];
arr[0]=0;
arr[1]=1;
arr[2]=1;
for (int i = 3; i <=n; i++) {
arr[i]=arr[i-1]+arr[i-2];
}
return arr[n];
}
}
消耗的內(nèi)存與時(shí)間情況
小發(fā)現(xiàn)
可以發(fā)現(xiàn)時(shí)間和空間往往二者不能兼得炼绘，要想減少時(shí)間就必須花費(fèi)一定的空間開銷來(lái)建立備忘錄來(lái)減少時(shí)間開銷
湊零錢問(wèn)題進(jìn)階動(dòng)態(tài)規(guī)劃
題目描述
Leetcode鏈接 322 零錢兌換：https://leetcode-cn.com/problems/coin-change/
**
給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來(lái)計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)俺亮。如果沒(méi)有任何一種硬幣組合能組成總金額疟呐，返回 -1。
你可以認(rèn)為每種硬幣的數(shù)量是無(wú)限的斟珊。
示例 1：
輸入：coins = [1, 2, 5], amount = 11
輸出：3
解釋：11 = 5 + 5 + 1
示例 2：
輸入：coins = [2], amount = 3
輸出：-1
示例 3：
輸入：coins = [1], amount = 0
輸出：0
示例 4：
輸入：coins = [1], amount = 1
輸出：1
示例 5：
輸入：coins = [1], amount = 2
輸出：2
1.暴力遞歸解法
代碼
class Solution {
int res = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if(coins.length == 0){
return -1;
}
findWay(coins,amount,0);
// 如果沒(méi)有任何一種硬幣組合能組成總金額富纸，返回 -1。
if(res == Integer.MAX_VALUE){
return -1;
}
return res;
}
public void findWay(int[] coins,int amount,int count){
if(amount < 0){
return;
}
if(amount == 0){
res = Math.min(res,count);
}
for(int i = 0;i < coins.length;i++){
findWay(coins,amount-coins[i],count+1);
}
}
}
消耗的內(nèi)存與時(shí)間情況
超時(shí)堵漱，超時(shí)了涣仿，說(shuō)明時(shí)間復(fù)雜度過(guò)高，需要通過(guò)加入備忘錄的反式來(lái)減少時(shí)間復(fù)雜度好港，一空間換時(shí)間
2.添加了備忘錄的解法
代碼
package com.pjh;
import com.sun.xml.internal.ws.api.model.MEP;
public class Leetcode322Solution11 {
int[] memory;
public int coinChange(int[] coins, int amount) {
/*coins硬幣的數(shù)組為空返回-1*/
if (coins.length==0){
return -1;
}
memory=new int[amount+1];
return findMin(coins,amount);
}
/*coins為存儲(chǔ)硬幣的數(shù)組钧汹，amount為當(dāng)前還剩的錢的數(shù)量，account為所用硬幣的數(shù)量*/
public int findMin(int[] coins,int amount){
/*結(jié)束遞歸的條件*/
if (amount==0){
return 0;
}
if (amount<0){
return -1;
}
/*判斷備忘錄中有沒(méi)有該值,有該值則直接返回*/
if (memory[amount]!=0){
return memory[amount];
}
int min1=Integer.MAX_VALUE;
for (int coin : coins) {
/*減去該硬幣的值進(jìn)行下一次遞歸*/
int temp= findMin(coins,amount-coin);
if (temp>=0&&temp+1<min1){
// 加1碗降，是為了加上得到res結(jié)果的那個(gè)步驟中塘秦，兌換的一個(gè)硬幣
min1=temp+1;
}
}
/*備忘錄記錄*/
memory[amount]=min1;
/*返回值*/
return memory[amount]==Integer.MAX_VALUE?-1:memory[amount];
}
}
消耗的內(nèi)存與時(shí)間情況
3.按照四個(gè)步驟列出動(dòng)態(tài)轉(zhuǎn)移方程
步驟
1.這個(gè)問(wèn)題最簡(jiǎn)單的情況（basecase）是什么
2.這個(gè)問(wèn)題有什么狀態(tài)
3.每個(gè)狀態(tài)可以做什么，可以做出什么選擇使得狀態(tài)發(fā)送變化
4.如何定義dp數(shù)組/函數(shù)的含義來(lái)表現(xiàn)“狀態(tài)”和選擇
分析
1.最基本條件即 錢的金額為0的時(shí)候所需硬幣數(shù)的0
2.狀態(tài)就是錢的總金額爪幻，隨著決策樹一層一層決策，金額不斷減少
3.發(fā)生狀態(tài)變化的條件挨稿，每選擇一枚硬幣就減少一定的金額
4.dp數(shù)組的定義叶组，定義數(shù)組存儲(chǔ)金額
狀態(tài)轉(zhuǎn)移方程如下
db（n）=
0，n==0
-1甩十，n<0
min{dp（n-coins）+1} , n>0
4.dp數(shù)組的迭代解法
代碼
class Solution {
public int coinChange(int[] coins, int amount) {
if(coins.length == 0){
return -1;
}
int[] memory = new int[amount + 1];
/*初始化數(shù)組，數(shù)組值設(shè)置為比傳入值大1即可*/
Arrays.fill(memory,amount+1);
/*初始化basecase*/
memory[0]=0;
/*遍歷ammount*/
for (int i = 0; i <= amount; i++) {
/*遍歷coins鸭轮，狀態(tài)遍歷的種類*/
for (int coin : coins) {
/*發(fā)生狀態(tài)變化的條件*/
if (i-coin<0) continue;
/*比較當(dāng)前值與memory的值誰(shuí)大*/
memory[i]=Math.min(memory[i], memory[i-coin]+1);
}
}
return memory[amount]==amount+1?-1: memory[amount];
}
}
