動態(tài)規(guī)劃問題的分類
- 求最大最小值
- 從左上角走到右下角路徑的最大數(shù)字和
- 最長上升子序列長度
- 計數(shù)
- 有多少種方式...
- 有多少種方法選出k個數(shù)使得和是sum
- 求存在性
- 取石子游戲屠阻，先手是否必勝
- 能不能選出k個數(shù)使得和是sum
常見動態(tài)規(guī)劃問題的類型
- 坐標型動態(tài)規(guī)劃(20%) ：二維數(shù)組下標就是坐標勺鸦，如機器人路線問題
- 序列型動態(tài)規(guī)劃(20%) ：
- 劃分型動態(tài)規(guī)劃(20%) ：給一個字符串或數(shù)組讓劃分成若干段滿足一些性質(zhì)
- 區(qū)間型動態(tài)規(guī)劃(15%) ：選擇連續(xù)區(qū)間而符合一定條件，f(i,j)
- 背包型動態(tài)規(guī)劃(10%) ：一定空間的背包最多帶多少物品的問題
- 最長序列型動態(tài)規(guī)劃(5%) ： 最長上升子序列等類似問題
- 博弈型動態(tài)規(guī)劃(5%) ： 博弈算出一個人是否必勝還是必敗或者勝率問題
- 綜合性動態(tài)規(guī)劃(5%) ： 綜合前面類型或和其他算法結(jié)合
- 動態(tài)規(guī)劃空間優(yōu)化問題，如數(shù)組降維
- 動態(tài)規(guī)劃打印路徑問題区拳，打印解
動態(tài)規(guī)劃問題解決步驟
- 0.為解題的每一步開辟一個等容量的數(shù)組存儲每一步的結(jié)果
- 1.確定狀態(tài)
- 最后一步：研究最優(yōu)策略的最后一步晨仑；
- 子問題：轉(zhuǎn)換成可不斷縮小規(guī)模的子問題；
- 2.轉(zhuǎn)移方程
- 根據(jù)可不斷縮小規(guī)模的子問題直接得到痴颊；
- 求最值用統(tǒng)計函數(shù)min赏迟，max等
- 求計數(shù)用累加
- 求可行性用or and布爾運算
- 根據(jù)可不斷縮小規(guī)模的子問題直接得到痴颊；
- 3.初始條件和邊界情況
- 細心考慮周全，某些初始條件可直接得到結(jié)果蠢棱；
- 4.計算順序
- 使用數(shù)組存儲每一步的計算結(jié)果锌杀，并在每一步利用之前的計算結(jié)果。
例題解析
一泻仙、求最值問題：
你有三種硬幣糕再，面值分別為2，5玉转，7亿鲜，每種硬幣都有足夠多。現(xiàn)在你需要買一本書需要27元冤吨，如何用最少的硬幣組合正好付清蒿柳，不需要對方找錢？
1.確定狀態(tài)
- 狀態(tài)在動態(tài)規(guī)劃中的作用屬于定海神針
- 簡單地說漩蟆，解動態(tài)規(guī)劃需要開一個數(shù)組垒探，數(shù)組的每個元素f[i]或者f[i][j]代表什么？
- 類似于解數(shù)學(xué)題中怠李，x圾叼，y，z代表什么捺癞？
- 確定狀態(tài)需要兩個意識
- 最后一步
雖然不知道最優(yōu)策略是什么夷蚊，但是最優(yōu)策略肯定是k枚硬幣a1，a2髓介，...,ak惕鼓，面值加起來是x
所以一定有一枚最后的硬幣：ak
除掉這枚硬幣，前面硬幣的面值加起來是27-ak
關(guān)鍵點1：不關(guān)心簽名的k-1枚是怎樣拼出27-ak的唐础，而且現(xiàn)在還不知道ak和k箱歧，但是確定簽名的硬幣拼出了27-ak
關(guān)鍵點2：因為是最優(yōu)策略矾飞，所以拼出27-ak的硬幣一定要最少。
- 子問題
- 所以我們就要去：最少用多少枚硬幣可以拼出27-ak
- 原問題是最少用多少枚硬幣拼出27
- 把原問題規(guī)模變小成為一個子問題
- 為了簡化定義呀邢，我們設(shè)狀態(tài)f(x) = 最少用多少枚硬幣拼出x
- 首先確定最后那枚硬幣ak是多少：
- 可能性：2洒沦，5，7
- 如果是2,最后枚數(shù)：f(27)= f(27-2) + 1
- 如果是5,最后枚數(shù)：f(27)= f(27-5) + 1
- 如果是7,最后枚數(shù)：f(27)= f(27-7) + 1
- 即f(27) = min{ f(27-2)+1, f(27-5)+1, f(27-7)+1}
- 可能性：2洒沦，5，7
- 最后一步
2.轉(zhuǎn)移方程
- 設(shè)狀態(tài)f[x] = 最少用多少枚硬幣拼出x
- 對于任意x： f[x] = = min{f[x-2]+1, f[x-5]+1, f[x-7]+1 }
3.初始條件和邊界情況
f[x] = = min{f[x-2]+1, f[x-5]+1, f[x-7]+1 }
兩個問題： x-2,x-5,x-7小于0怎么辦价淌？ 什么時候停下來申眼？
-
如果不能拼出y，則定義f[y]= 正無窮
- 例如f[-1]=f[-2]=...=正無窮
所以f[1] = min{f[-1]+1, f[-4]+1, f[-6]+1} = 正無窮蝉衣，表示拼不出來1
初始條件：f[0] = 0
4.計算順序
- 拼出x所需要的最少硬幣數(shù)：f[x] = min{f[x-2]+1, f[x-5]+1, f[x-7]+1 }
- 初始條件：f[0] = 0
- 然后計算f[1],f[1],...f[27]
- 當我們計算到f[x]時豺型，f[x-2], f[x-5], f[x-7]都已經(jīng)得到結(jié)果了。
func CoinChange(coinList []int, total int) int {
// 0,....,n : [n+1]
// 0,....,n-1 : [n]
stepList := make([]int, total+1) // 存儲每1元需要多少枚硬幣的結(jié)果
coinNum := len(coinList) // 硬幣的類型數(shù)量
// 初始條件
stepList[0] = 0
var i, j int
for i = 1; i <= total; i++{
// 每一元的情況需要多少枚硬幣,默認設(shè)置無窮大
stepList[i] = math.MaxInt64
// 最后一枚硬幣 stepList[j]
// stepList[i]= math.Min(stepList[i-coinList[j]])+1,stepList[i])
for j = 0; j < coinNum; j++ {
// total需大于硬幣面值
if i >= coinList[j] && stepList[i-coinList[j]] != math.MaxInt64 {
// 轉(zhuǎn)移方程
stepList[i] = int(math.Min(float64(stepList[i-coinList[j]])+1, float64(stepList[i])))
}
}
}
if stepList[total] == math.MaxInt64 {
stepList[total] = -1
}
return stepList[total]
}
二买乃、求計數(shù)：
給定m行n列的網(wǎng)格姻氨，有一個機器人從左上角(0,0)出發(fā)，每一步可以向下或者向右走一步剪验，問有多少種不同的方式走到右下角肴焊。
1.確定狀態(tài)
- 最后一步：
- 無論機器人用何種方式到達右下角，總有最后挪動的一步：向右或向下功戚；
- 右下角坐標設(shè)置為(m-1,n-1)
- 那么前一步機器人一定是在(m-2,n-1)或者(m-1,n-2)
- 子問題:
- 如果機器人有X種方式從左上角走到(m-2,n-1)娶眷，有Y種方式從左上角走到(m-1,n-2)，則機器人有X+Y種方式走到 - 如果機器人有X種方式從左上角走到(m-2,n-1)啸臀，有Y種方式從左上角走到(m-1,n-2)届宠，則機器人有X+Y種方式走到(m-1,n-1)。 =》 數(shù)學(xué)組合中的加法原理
- 問題轉(zhuǎn)化為機器人有多少種方式從左上角走到(m-2,n-1)和(m-1,n-2)乘粒；
- 原題要求有多少種方式從左上角走到(m-1,n-1)豌注。
- 轉(zhuǎn)化子問題：狀態(tài)：設(shè)f[i][j]為機器人有多少種方式從左上角走到(i,j)
2.轉(zhuǎn)移方程
- 對于任一格子(i,j)：f[i][j] = f[i-1][j] + f[i][j-1]
3.初始條件和邊界情況
- 初始條件：f[0][0] = 1，因為機器人只有一種方式到左上角
- 邊界情況：i=0或j=0灯萍，則前一步只能由一個方向過濾：f[i][j] = 1
4.計算順序
- f[0][0] = 1
- 計算第0行：f[0][0]轧铁，f[0][1]，...,f[0][n-1]
- 計算第1行：f[1][0]旦棉，f[1][1]齿风，...,f[1][n-1]
- ...
- 計算第m-1行：f[m-1][0]，f[m-1][1]绑洛，...,f[m-1][n-1]
- 答案是：f[m-1][n-1]
- 時間復(fù)雜度（計算步數(shù)）：O(MN)救斑，空間復(fù)雜度（數(shù)組大小）：O(MN)
// 輸入行列參數(shù)m,n
func UniquePaths(m, n int) int{
// 開一個二維數(shù)組m行,存儲走到當前每一格的可能性步數(shù)
f := make([][]int, m, m)
var i, j int
for i = 0; i < m; i++ { // row:top to bottom
// 每行開n列的數(shù)組
f[i] = make([]int, n, n)
for j = 0; j < n; j++ { // column:left to right
if i == 0 || j == 0 {
// 初始格為1
f[i][j] = 1
}else {
// 轉(zhuǎn)移方程:當前格 = 上一格往下的情況 + 上一格往右的情況
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
}
// 只需返回最后一格作為結(jié)果即可
return f[m-1][n-1]
}
三真屯、求可能性：
有n塊石頭分別在x軸的0,1,...,n-1位置脸候，一只青蛙在石頭0，想跳到石頭n-1，如果青蛙在第i塊石頭上纪他，它最多可以向右跳距離ai鄙煤，問青蛙能否跳到石頭n-1晾匠？
例子：輸入a=[2,3,1,1,4],輸出true茶袒；輸入a=[3,2,1,0,4],輸出false;
1.確定狀態(tài)
- 最后一步：
- 如果青蛙能跳到最后一塊石頭n-1，我們考慮它跳的最后一步
- 這一步從石頭i跳過來凉馆，i<n-1
- 這需要兩個條件同時滿足：
- 青蛙可以跳到石頭i (不好判斷)
- 最后一步不超過跳躍的最大距離：n-1-i<=ai （好判斷）
- 子問題:
- 我們需要知道青蛙能不能跳到石頭i(i<n-1)
- 而我們原來要求青蛙能不能跳到石頭n-1
- 狀態(tài)：設(shè)f[j]表示青蛙能不能跳到石頭j
2.轉(zhuǎn)移方程
- 設(shè)f[j]表示青蛙能不能跳到石頭j
- f[j] = OR(f[i] AND i + a[i] >= j) (0<=i<j)
- f[j] : 表示青蛙能不能跳到石頭j薪寓；
- 0<=i<j ： 表示枚舉上一個跳到的石頭i；
- f[i] AND i ： 表示青蛙能不能跳到石頭i澜共；
- a[i] >= j ： 表示最后一步的距離不能超過ai
3.初始條件和邊界情況
初始條件:設(shè)f[i]表示青蛙能不能跳到石頭i
邊界條件：f[0] = true向叉，因為青蛙一開始就在石頭0
4.計算順序
- 設(shè)f[i]表示青蛙能不能跳到石頭i
- f[j] = OR(f[i] AND i + a[i] >= j) (0<=i<j)
- f[0] = true
- 計算f[1],f[1],...f[n-1]
- 答案是f[n-1]
- 時間復(fù)雜度：O(N2)，空間復(fù)雜度（數(shù)組大朽露）：O(N)
func CanJump(list []int) bool {
// 石頭塊數(shù)
n := len(list)
// 開辟數(shù)組,存儲跳到每個石頭的可能性
canList := make([]bool, n, n)
canList[0] = true // 初始位置0石頭肯定可以
// 從位置1開始
for j := 1; j < n; j++ {
canList[j] = false // 假設(shè)不可行
// 從當前石頭i開始
// 最后一跳是i到j(luò),j必須在i后面
for i := 0; i < j; i++ {
// 轉(zhuǎn)移方程
if canList[i] && i+list[i] >= j {
canList[j] = true
break
}
}
}
return canList[n-1]
}
