動態(tài)規(guī)劃
動態(tài)規(guī)劃是一種將復雜問題分解成更小的子問題求解的技術
要注意動態(tài)規(guī)劃和分而治之是不同的方法传蹈。分而治之是把問題分解為相互獨立的子問題凛篙，然后組合她們的答案。而動態(tài)規(guī)劃是一種將問題分解成相互依賴的子問題踱蠢。
用動態(tài)規(guī)劃解決問題時，需要遵循三個重要步驟 :
- 定義子問題
- 實現(xiàn)要反復執(zhí)行來解決子問題的部分
- 識別并求解出邊界條件
或者說 :
- 通過最后一步和子問題確定狀態(tài) dp
- 列出狀態(tài)轉(zhuǎn)移方程
- 確定編程的邊界條件 衷畦、 初始條件
他有一些著名的問題 :
- 背包問題 : 給出一組對象，該對象有值與容量知牌，目標是找出總值最大的項目集合祈争，前提是必須小于背包的容量
- 最長公共子序列 : 找出一組序列最長的公共子序列(可以根據(jù)另一個序列刪除元素，但不影響剩下元素的順序)
- 矩陣鏈相乘
- 硬幣找零
- 圖的全源最短路徑 : 對所有頂點對(u,v)角寸，找出從頂點u道頂點v的最短路徑菩混，有個算法叫做floyd-warshall算法
1. 最少硬幣找零問題
美國有以下面額硬幣 1、 5扁藕、 10沮峡、 25
如果要找36美分的零錢，我們可以用1個25 1個10 一個1
如何將這個算法轉(zhuǎn)為算法
以下是書本的算法
/**
*
* @param {array} coins 硬幣面額
*/
function minCoinChange (coins) {
let coins = coins
cache = {}
/**
* 找零方法
* @param {number} 需要找零的總額
*/
this.makeChange = function (amount) {
// 提升作用域
let self = this
// 不存在則返回控
if (!amount) {
return []
}
// memorize
if (cache[amount]) {
return cache[amount]
}
let min = [], newMin, newAmount;
// 循環(huán)硬幣面額
for (let i = 0; i < coins.length; i++) {
let coin = coins[i] // 硬幣額
// 新的總額 = 總額 - 現(xiàn)在的硬幣額
newAmount = amount - coin
// 如果新的總額大于0 則遞歸 終止條件為新的總額小于0
if (newAmount >= 0) {
newMin = self.makeChange(newAmount)
}
if (newAmount >= 0
&& (newMin.length < min.length - 1 || !min.length)
&& (newMin.length || !newAmount)
) {
min = [coin].concat(newMin)
console.log('new Min' + min + ' for ' + amount)
}
}
return (cache[amount] = min)
}
}
以下是我根據(jù)九章算法公開課寫的
/**
*
* @param {*} coins 硬幣數(shù)組
* @param {*} count 要找零的值
*/
function minChange (coins, count) {
// 最后一步 : 結(jié)果總是 f(count - coins[i]) + 1 枚硬幣
// 子問題 : 最少用多少枚硬幣可以拼出 f(count - coins[i])
// 確定狀態(tài) : f(count-coins[i]) = 最少用多少枚硬幣拼出count-coins[i]這個值
// 狀態(tài)轉(zhuǎn)移方程 : f(count) = Math.min(f(count-coins[0])+1,...f(count-coins[n-1])+1)
// 確定邊界條件 1. i >= coin 2. i - coins[j] > 0 3. i !== coin
const states = []
states[0] = 0
// 根據(jù)狀態(tài)轉(zhuǎn)移方程逐個求值
for (let i = 1; i <= count; i++) {
states[i] = Infinity
for (let coin of coins) {
// 邊界條件
if (i >= coin && states[i - coin] !== Infinity) {
states[i] = Math.min(states[i - coin] + 1, states[i])
}
}
}
return states[count]
}
console.log(Infinity > 0)
console.log(minChange([1, 5, 10, 25], 35)) // logs 2
2. 背包問題
給定一個固定大小亿柑、能夠攜帶重量W的背包邢疙，以及一組有價值和重量的物品，找出一個最佳的解決方案望薄，使得轉(zhuǎn)入背包的物品總重量不超過W疟游、且價值最大
| 物品 | 重量 | 價值 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
- 定義狀態(tài)
- 總問題 : 重量為w的背包，怎么放價值最大 ?
- 最后一步 : 無論背包有多大痕支，它總會放一種物品
f[i][w] = 第i種物品放入背包容量為v的最大價值 - 子問題應該是 ： 當我放下或不放下該容量的物品時颁虐，剩下容量的怎么放最大價值是多少 ?
- 狀態(tài) : f[i][w] = 當我放下或不放下該容量的物品時，剩下容量的怎么放最大價值是多少
- 狀態(tài)轉(zhuǎn)移方程 :
f[i][w] = Math.max( (i.v + f[i][w-i.w]),f[i][w-1] )
- 確定編程的邊界條件
- 初始條件 :
f[0][0] = 0 - 邊界條件 :
- 當i-1>=0時卧须，且w不滿足第i種物品重量另绩，則f[i][w] = f[i-1][w]
- 當i=0時，i-1<0花嘶，此時若w不滿足第i種物品重量笋籽，則f[i][w] = 0
- 當w > 前i種物品weight總和，則f[i][w] = f[i-1][w]
const products = [
{
name: '鉛筆',
weight: 1,
value: 17
},
{
name: '蜂蜜',
weight: 2,
value: 15
},
{
name: '松茸',
weight: 4,
value: 20
},
{
name: '紅寶石',
weight: 10,
value: 100
}
]
function knapSack (capacity, products) {
const states = []
let max = 0
for (let i in products) {
states[i] = []
states[i][0] = 0
}
for (let i in products) {
let curPro = products[i]
// 計算前i種物品重量總和
let lastWeight = products.reduce((account,{weight},index)=> {
return index <=i ? account + weight : account
},0)
for (let w = 1; w <= capacity; w++) {
let res1 = 0
let res2 = 0
if (w >= curPro.weight && w <= lastWeight) {
res1 = curPro.value + (w - curPro.weight >= 0 && i>0 ? states[i][w - curPro.weight] : 0)
} else {
res1 = i >0 ? states[i][w] = states[i-1][w] : states[i][w] = 0
}
res2 = states[i][w - 1]
states[i][w] = Math.max(res1, res2)
max = states[i][w] > max ? states[i][w] : max
}
}
console.log(max)
}
knapSack(6, products)
3. 機械人走路
看下圖察绷，問 : 機械人共有多少種方式走到右下角
圖片.png
- 定義狀態(tài)
- 最后一步 : 無論機械人怎么走到最后的格子干签，都是從上面格子，或者下面格子走過去的
- 子問題 : 假設最后的格子坐標為(n,m) 則一共有多少種方式走到(n-1,m) 和 (n,m-1)
- 狀態(tài) : f(n,m) = 一共有多少種方式走到(n,m)
- 狀態(tài)轉(zhuǎn)移方程
- f(n,m) = f(n-1,m) + f(n,m+1)
- 確定編程的邊界條件
- 初始條件 : f(0,0) = 1
- 邊界條件 : f(0,m) 或是 f(m,0) = 1
function robotWay(n,m) {
const arr = []
arr[0][0] = 1
for(let i =0;i<n;i++) {
for(let j=0;j<m;j++) {
if(i===0 || j ===0) {
f[i][j] = 1
} else {
f[i][j] = f[i-1][j] + f[i][j-1]
}
}
}
return arr[n-1][m-1]
}
console.log(robotWay[2][2])
4. 跳躍游戲
描述 :
- 有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
- 確定狀態(tài)
- 總問題 : 青蛙能不能跳到石頭n
- 最后一步 : 最后一跳肯定是青蛙所在位置i的石頭數(shù)a[i]>=最后下標n所在位置i a[i] >= n-i
- 子問題 : 青蛙能不跳到石頭i(i<n)
- 狀態(tài) : f(i) = 青蛙能不能跳到石頭i
- 轉(zhuǎn)移方程
f(n) = [f(0) && a[0]>= n-0,....f(i) && a[i] >= n-i].some(item=>item)
- 初始條件
- f[0] 肯定為true
const arr1 = [2,3,1,1,4]
const arr2 = [3,2,1,0,4]
function jumpGame(arr) {
const f = new Array(arr.length).fill(false)
for(let i =0 ;i<f.length;i++) {
if(i === 0) {
f[i] = true
} else {
let j = -1
while(++j<i) {
if(f[j] && arr[j] >= i-j ) {
f[i] = true
}
}
}
}
return f[arr.length-1]
}
console.log(jumpGame(arr1)) // true
console.log(jumpGame(arr2)) // false
5. 最長公共子序列(LCS)
找出連個字符串序列的最長子序列的長度，最長子序列是指闸度，在兩個字符串序列中以相同順序出現(xiàn).
但不要求連續(xù)(非字符字串)的字符串序列
a = 'acbacd'
b = 'abcadf'
// LCS : 長度為4的'acad'
- 確定狀態(tài)
- 總問題 : 找出兩個字符串序列的最長子序列的長度
- 最后一步 : 設f[i][j] = 字符串A從0到索引i與字符串B從0到索引j的最長公共子序列 并且A[i]與B[j]相等 且f[i-1][j-1] + 1 = f[i][j]
- 子問題 : A[i]與B[j]相等時,f[i-1][j-1]的子序列長度是多少? (找不到子問題)
- 定義狀態(tài)：f[i][j] = 字符串A從0到索引i與字符串B從0到索引j的最長公共子序列
- 定義狀態(tài)轉(zhuǎn)移方程
f[i][j] = A[i] === B[j] ? f[i-1][j-1] + 1 : Math.max(dp[i-1][j],dp[i][j-1])
為什么是
Math.max(dp[i-1][j],dp[i][j-1])? 因為當子序列acb與abc時,它A[i]!==B[j] 此時它的子序列有兩種可能,一是acb與ab 二是ac與abc 所以應考慮兩種情況,取其最大值
- 確定編程邊界條件
- 初始條件 : f[0][0] = A[0] === B[0] ? 1 : 0
- 邊界條件 : 當 i===0 || j === 0 時,f[i][j]最多等于1,f[i][j] = A[i] === B[j] ? 1 : 0,如果A[i] !== B[j],則f[i][j] = i === 0? f[i][j-1] : f[i-1][j]
function lcs(strA,strB) {
let dp = [],
initState = strA[0] === strB[0] ? 1 : 0 ,
max = initState
for(let i=0;i<strA.length;i++) {
dp[i] = []
for(let j=0;j<strB.length;j++) {
if(i === 0 || j === 0 ) {
dp[i][j] = initState
} else {
dp[i][j] =strA[i] === strB[j] ? dp[i-1][j-1] +1 : i>j? dp[i-1][j] : dp[i][j-1]
max = dp[i][j] > max ? dp[i][j] : max
}
}
}
return max
}
console.log(lcs('acbacd','abcadf')) // logs 4
