动态规划

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。简单来说 他是一种设计方法。

动态规划

特征

当你发现一个问题具有如下特征的时候,很有可能可以依赖动态规划来解决

  • 一个问题的最优解包含其子问题的最优解 也就是俗称的最优子结构

最长公共子序列

最长公共子序列利用排列组合的方式去找几乎是不太可行的,因为他的复杂度是指数级

所以我们需要一种更加高效的方式来为我们解决这类问题。

动态规划 example

让我们看看如何用动态规划来解决最长公共子序列问题

  1. 找出序列x和y的LCS的长度
  2. 扩展如上算法,并找出这个LCS,

OK 现在我们的问题开始转化,变成了如何找到LCS的长度问题,那么,我们该怎么做呢?

|S| 代表序列S的长度 重点关注x y 的前缀 // 比如说一个序列X = <a,b,c,d> 那么X3 = <a,b,c> 其实就是把一个序列切成有i个值的片段 定义 C[i,j] = |LCS(x[1,i],y[1,j])| 这里的C[i,j] 就是x与y的LCS长度 C[m,n] = LCS(x,y)

伪代码

 C[i,j] =  // i和j代表的是 xi yj序列片段下的LCS长度 
  if(i==0 || j == 0) return 0 //一个序列为空 肯定为0
  if(i>0 && j>0 && xi == yj) return C[i-1,j-1] + 1 // 匹配上了 在这一层加1 继续求子问题  +1 操作只在这里发生 这里是xi代表的是序列XI中的最后一个 是下标
  if(i>0 && j>0 && xi !== yj) return max(C(i-1,j),C(i,j-1)) // 没有匹配上 继续向下 寻求匹配,由于不知道后续 开辟两条路线

这个东西的复杂度大概是 O(2 ^ (m+n)) 当然也是指数级别的 不过可以通过缓存技术进行加速

在我看来这个递归式的图形大概是这样 可能有点丑,不过这是我的理解

想象一个人在这两个序列上走路 从右到左 如果他发现左脚和右脚内容一样 + 1 ,如果发现不一样,那么这里就会出现问题,到底是左脚迈一步,还是右脚迈一步,如果都迈,那么可能会错过x + 1 与 当前的y 相等的情况,所以只能创建两个分支,迈左脚和迈右脚都试试。## 动态规划

特征

当你发现一个问题具有如下特征的时候,很有可能可以依赖动态规划来解决

  • 一个问题的最优解包含其子问题的最优解 也就是俗称的最优子结构
  • 重叠的子问题

最长公共子序列

最长公共子序列利用排列组合的方式去找几乎是不太可行的,因为他的复杂度是指数级

所以我们需要一种更加高效的方式来为我们解决这类问题。

动态规划 example

让我们看看如何用动态规划来解决最长公共子序列问题

  1. 找出序列x和y的LCS的长度
  2. 扩展如上算法,并找出这个LCS,

OK 现在我们的问题开始转化,变成了如何找到LCS的长度问题,那么,我们该怎么做呢?

|S| 代表序列S的长度 重点关注x y 的前缀 // 比如说一个序列X = <a,b,c,d> 那么X3 = <a,b,c> 其实就是把一个序列切成有i个值的片段 定义 C[i,j] = |LCS(x[1,i],y[1,j])| 这里的C[i,j] 就是x与y的LCS长度 C[m,n] = LCS(x,y)

伪代码

 C[i,j] =  // i和j代表的是 xi yj序列片段下的LCS长度 
  if(i==0 || j == 0) return 0 //一个序列为空 肯定为0
  if(i>0 && j>0 && xi == yj) return C[i-1,j-1] + 1 // 匹配上了 在这一层加1 继续求子问题  +1 操作只在这里发生 这里是xi代表的是序列XI中的最后一个 是下标
  if(i>0 && j>0 && xi !== yj) return max(C(i-1,j),C(i,j-1)) // 没有匹配上 继续向下 寻求匹配,由于不知道后续 开辟两条路线

这个东西的复杂度大概是 O(2 ^ (m+n)) 当然也是指数级别的 不过可以通过缓存技术进行加速

在我看来这个递归式的图形大概是这样 可能有点丑,不过这是我的理解

想象一个人在这两个序列上走路 从右到左 如果他发现左脚和右脚内容一样 + 1 ,如果发现不一样,那么这里就会出现问题,到底是左脚迈一步,还是右脚迈一步,如果都迈,那么可能会错过x + 1 与 当前的y 相等的情况,所以只能创建两个分支,迈左脚和迈右脚都试试。

从分解子问题的角度上看,首先他设想已经拥有了最长子序列长度K 长度为k-1的LCS,并尝试寻找下一个可以让当前LCS + 1的匹配对应值,这很像分治法,设想我们已经快完成了,完成最后一步,其实是一步步的拆分问题,动态规划与普通递归的差别就在于,动态规划的子结构必须拥有最优子结构特性。分治法分解的是不相关的子问题,而动态规划分解的是重叠的子问题。

性能

动态规划算法会分解 重叠子问题 这意味着很多动态规范的算法都能用缓存技术来提高性能,比如LCS问题就能保存个ij的LCS在有结果的时候直接返回。

求LCS长度的实现 备忘法

let s1 = [10, 5, 3, 90, 20, 58, 78, 20, 76, 2304, 230]
let s2 = [10, 3, 20, 78, 200, 40, 20, 230]


const LCS_LENGTH = (...args) => {
  let mem = []
  const _LCS = (s1, s2, i, j) => {
    if (mem['' + i + j]) return mem['' + i + j]
    if (i < 0 || j < 0) return 0
    if (s1[i] === s2[j]) {
      return mem['' + i + j] = _LCS(s1, s2, i - 1, j - 1) + 1
    } else {
      return Math.max(_LCS(s1, s2, i - 1, j), _LCS(s1, s2, i, j - 1))
    }
  }
  return _LCS(...args)
}

LCS_LENGTH(s1, s2, s1.length - 1, s2.length - 1)

时间复杂度 O(m*n) 空间O(m*n)

改进 自底向上的设计 真!动态规划

let s2 = ['A', 'B', 'C', 'B', 'D', 'A', 'B', 'F', 'G', 'J']
let s1 = ['B', 'D', 'C', 'A', 'B', 'A', 'F', 'H', 'J']

const LCS_TABLE = (s1, s2) => {
  let x = s1.length
  let y = s2.length
  // 需要保证表格的便利与数组的访问同意 也就是从1 开始
  // 所以需要在前面将数组踮起 并且为了避免越界 需要在获取长度之后进行
  s1.unshift(null)
  s2.unshift(null)
  // 以下两个循环都是为了打出一个边界 也就是表格的最顶层和最左层都是0
  let table = []
  for (let i = 0; i <= x; i++) {
    table[i] = []
    table[i][0] = {
      val: 0
    }
  }
  for (let i = 0; i <= y; i++) {
    table[0][i] = {
      val: 0
    }
  }
  // 正式开始
  for (let i = 1; i <= x; i++) {
    for (let j = 1; j <= y; j++) {
      // 找到匹配 填入左上箭头
      if (s1[i] === s2[j]) {
        table[i][j] = {
          val: table[i - 1][j - 1].val + 1,
          lt: true
        }
      } else if (table[i - 1][j].val >= table[i][j - 1].val) {
        table[i][j] = {
          val: table[i - 1][j].val,
          top: true
        }
      } else {
        table[i][j] = {
          left: true,
          val: table[i][j - 1].val
        }
      }
    }
  }
  return table
}

let table = LCS_TABLE(s1, s2)

const printLCS = (table, X, i, j) => {
  if (i === 0 || j === 0) return
  if (table[i][j].lt) {
    console.log(X[i])
    return printLCS(table, X, i - 1, j - 1)
  }
  if (table[i][j].top) {
    return printLCS(table, X, i - 1, j)
  }
  return printLCS(table, X, i, j - 1)
}

printLCS(table, s1, s1.length - 1, s2.length - 1)

算法复杂度O(m*n)

感觉特别像填表游戏,就是拿到一个表格然后按照规定去填表,可以分为两部分

填表

  1. Xi 与 Yi 匹配就填↖箭头
  2. 如果不匹配 在左边的框和上面框里找出拥有最大LCS的那个(你看 找最优子结构 特点来了) 搜索
  3. 找到匹配就输出
  4. 没匹配就往箭头的方向去走

关键就在于如何去一步步的拼接那个LCS链路 不断的在比较短的LCS上 去接更长的LCS的 如此反复 就能获取到LCS

不过这个LCS其实在大多数情况下并不唯一,和你的遍历顺序有非常大的关系。