算法图解第9章——动态规划

动态规划

先解决子问题，再解决大问题。

动态规划可以在给定约束条件下找到最优解，没有可公用的公式。

利用网格来解决。各行的排列顺序无关紧要。可以逐列也可以逐行填充网格。单元格中的值通常就是你要优化的值。

每个单元格都是一个子问题。

当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。

如何绘制网格

单元格中的值是什么？

如何将这个问题划分为子问题？

网格的坐标轴是什么？

//将物品放入包内
//物品重量和价值
let sth = {}
sth['gita']=[1,1500]
sth['viedo']=[4,3000]
sth['computer']=[3,2000]
sth['ring']=[0.5,1000]
//包的容量
let bags = [0.5,1,1.5,2,2.5,3,3.5,4]
let bagsConversion = 2
//网格
let sthArr = Object.keys(sth);
let cellB = []
//包的容量做横向坐标
for (let bi = 0; bi < sthArr.length; bi++) {
  //网格增加一行
  cellB.push([])
  //获取物品参数
  let sthParameter = sthArr[bi]
  //物品做竖向坐标
  for (var bj = 0; bj < bags.length; bj++) {
    //单元格的值
    let bagWeight = bags[bj]
    //上一个单元格的值
    let topValue = (bi === 0) ? 0 : cellB[bi-1][bj]
    //重量
    let sthWeight = sth[sthParameter][0]
    //价值
    let topLeftValue = 0
    if(sthWeight <= bagWeight){
      //价值
      let sthValue = sth[sthParameter][1]
      //剩余容量的值
      let lastValue = ((bi === 0) || (bagWeight <= sthWeight)) ? 0 : cellB[bi-1][(bagWeight-sthWeight)*bagsConversion-1]
      topLeftValue = sthValue + lastValue;
    }
    //取最大值
    cellB[bi][bj] = Math.max(topValue, topLeftValue)
  }
}
console.log(cellB);
//[ [ 0, 1500, 1500, 1500, 1500, 1500, 1500, 1500 ],
  [ 0, 1500, 1500, 1500, 1500, 1500, 1500, 3000 ],
  [ 0, 1500, 1500, 1500, 1500, 2000, 2000, 3500 ],
  [ 1000, 1500, 2500, 2500, 2500, 2500, 3000, 3500 ] ]//

最长公共子串

例如：比较两个单词

const wordA = 'blue'
const wordB = 'clues'

1.如果连个字母不相同，值为0

2.如果两个字母相同，值为左上角邻居的值➕1

let cell=[];
for (var i = 0; i < wordA.length; i++) {
  cell.push([]);
  for (var j = 0; j < wordB.length; j++) {
    let wA = wordA[i]
    let wB = wordB[j]
    if(wA === wB){
      let iSet = (i === 0 || j === 0) ? 0 : cell[i-1][j-1]
      cell[i][j] = iSet + 1
    } else {
      cell[i][j] = 0
    }
  }
}
console.log(cell);
//[ [ 0, 0, 0, 0, 0 ],
  [ 0, 1, 0, 0, 0 ],
  [ 0, 0, 2, 0, 0 ],
  [ 0, 0, 0, 3, 0 ] ]//

答案是网格中最大的数字，它可能并不位于最后的单元格中。

最长公共子序列

1.如果两个字母不同，就选择上方和左方邻居中最大的那个

2.如果两个字母相同，就选择左上方单元格的值➕1

let cellL = [];
for (var ii = 0; ii < wordA.length; ii++) {
  cellL.push([])
  for (var jj = 0; jj < wordB.length; jj++) {
    let wLA = wordA[ii]
    let wLB = wordB[jj]
    if(wLA === wLB){
      let ijSet = (ii === 0 || jj === 0) ? 0 : cellL[ii-1][jj-1]
      cellL[ii][jj] = ijSet + 1
    } else {
      let iiSet = (ii === 0) ? 0 : cellL[ii-1][jj]
      let jjSet = (jj === 0) ? 0 : cellL[ii][jj-1]
      cellL[ii][jj] = Math.max(iiSet, jjSet)
    }
  }
}
console.log(cellL);
//[ [ 0, 0, 0, 0, 0 ],
  [ 0, 1, 1, 1, 1 ],
  [ 0, 1, 2, 2, 2 ],
  [ 0, 1, 2, 3, 3 ] ]//

动态规划的应用场景：

1.DNA相似性

2.git diff

3.用户上传的资料是否是盗版

4.word的断字功能