动态规划

动态规划是一种将复杂问题分解成更小的子问题求解的技术

要注意动态规划和分而治之是不同的方法。分而治之是把问题分解为相互独立的子问题，然后组合她们的答案。而动态规划是一种将问题分解成相互依赖的子问题。

用动态规划解决问题时，需要遵循三个重要步骤 :

• 定义子问题
• 实现要反复执行来解决子问题的部分
• 识别并求解出边界条件

或者说 :

• 通过最后一步和子问题确定状态 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

1. 定义状态

• 总问题 : 重量为w的背包，怎么放价值最大 ?
• 最后一步 : 无论背包有多大，它总会放一种物品

  f[i][w] = 第i种物品放入背包容量为v的最大价值
  

• 子问题应该是 ： 当我放下或不放下该容量的物品时，剩下容量的怎么放最大价值是多少 ?
• 状态 : f[i][w] = 当我放下或不放下该容量的物品时，剩下容量的怎么放最大价值是多少

2. 状态转移方程 :

f[i][w] = Math.max( (i.v + f[i][w-i.w]),f[i][w-1] ) 

3. 确定编程的边界条件

• 初始条件 : 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

1. 定义状态

• 最后一步 : 无论机械人怎么走到最后的格子，都是从上面格子，或者下面格子走过去的
• 子问题 : 假设最后的格子坐标为(n,m) 则一共有多少种方式走到(n-1,m) 和 (n,m-1)
• 状态 : f(n,m) = 一共有多少种方式走到(n,m)

2. 状态转移方程

• f(n,m) = f(n-1,m) + f(n,m+1)

3. 确定编程的边界条件

• 初始条件 : 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

1. 确定状态

• 总问题 : 青蛙能不能跳到石头n
• 最后一步 : 最后一跳肯定是青蛙所在位置i的石头数a[i]>=最后下标n所在位置i a[i] >= n-i
• 子问题 : 青蛙能不跳到石头i(i<n)
• 状态 : f(i) = 青蛙能不能跳到石头i

2. 转移方程

f(n) = [f(0) && a[0]>= n-0,....f(i) && a[i] >= n-i].some(item=>item)

3. 初始条件

• 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'

1. 确定状态

• 总问题 : 找出两个字符串序列的最长子序列的长度
• 最后一步 : 设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的最长公共子序列

2. 定义状态转移方程

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 所以应考虑两种情况,取其最大值

3. 确定编程边界条件

• 初始条件 : 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