动态规划
动态规划是一种将复杂问题分解成更小的子问题求解的技术
要注意动态规划和分而治之是不同的方法。分而治之是把问题分解为相互独立的子问题，然后组合她们的答案。而动态规划是一种将问题分解成相互依赖的子问题。
用动态规划解决问题时，需要遵循三个重要步骤 :
- 定义子问题
- 实现要反复执行来解决子问题的部分
- 识别并求解出边界条件
或者说 :
- 通过最后一步和子问题确定状态 dp
- 列出状态转移方程
- 确定编程的边界条件 、 初始条件
他有一些著名的问题 :
- 背包问题 : 给出一组对象，该对象有值与容量，目标是找出总值最大的项目集合，前提是必须小于背包的容量
- 最长公共子序列 : 找出一组序列最长的公共子序列(可以根据另一个序列删除元素，但不影响剩下元素的顺序)
- 矩阵链相乘
- 硬币找零
- 图的全源最短路径 : 对所有顶点对(u,v)，找出从顶点u道顶点v的最短路径，有个算法叫做floyd-warshall算法
1. 最少硬币找零问题
美国有以下面额硬币 1、 5、 10、 25
如果要找36美分的零钱，我们可以用1个25 1个10 一个1
如何将这个算法转为算法
以下是书本的算法
/**
*
* @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;
// 循环硬币面额
for (let i = 0; i < coins.length; i++) {
let coin = coins[i] // 硬币额
// 新的总额 = 总额 - 现在的硬币额
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)
}
}
以下是我根据九章算法公开课写的
/**
*
* @param {*} coins 硬币数组
* @param {*} count 要找零的值
*/
function minChange (coins, count) {
// 最后一步 : 结果总是 f(count - coins[i]) + 1 枚硬币
// 子问题 : 最少用多少枚硬币可以拼出 f(count - coins[i])
// 确定状态 : f(count-coins[i]) = 最少用多少枚硬币拼出count-coins[i]这个值
// 状态转移方程 : 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
// 根据状态转移方程逐个求值
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的背包，以及一组有价值和重量的物品，找出一个最佳的解决方案，使得转入背包的物品总重量不超过W、且价值最大
| 物品 | 重量 | 价值 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
- 定义状态
- 总问题 : 重量为w的背包，怎么放价值最大 ?
- 最后一步 : 无论背包有多大，它总会放一种物品
f[i][w] = 第i种物品放入背包容量为v的最大价值 - 子问题应该是 ： 当我放下或不放下该容量的物品时，剩下容量的怎么放最大价值是多少 ?
- 状态 : f[i][w] = 当我放下或不放下该容量的物品时，剩下容量的怎么放最大价值是多少
- 状态转移方程 :
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
- 定义状态
- 最后一步 : 无论机械人怎么走到最后的格子，都是从上面格子，或者下面格子走过去的
- 子问题 : 假设最后的格子坐标为(n,m) 则一共有多少种方式走到(n-1,m) 和 (n,m-1)
- 状态 : f(n,m) = 一共有多少种方式走到(n,m)
- 状态转移方程
- 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
- 确定状态
- 总问题 : 青蛙能不能跳到石头n
- 最后一步 : 最后一跳肯定是青蛙所在位置i的石头数a[i]>=最后下标n所在位置i a[i] >= n-i
- 子问题 : 青蛙能不跳到石头i(i<n)
- 状态 : f(i) = 青蛙能不能跳到石头i
- 转移方程
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)
找出连个字符串序列的最长子序列的长度，最长子序列是指，在两个字符串序列中以相同顺序出现.
但不要求连续(非字符字串)的字符串序列
a = 'acbacd'
b = 'abcadf'
// LCS : 长度为4的'acad'
- 确定状态
- 总问题 : 找出两个字符串序列的最长子序列的长度
- 最后一步 : 设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]的子序列长度是多少? (找不到子问题)
- 定义状态：f[i][j] = 字符串A从0到索引i与字符串B从0到索引j的最长公共子序列
- 定义状态转移方程
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
网友评论