算法导论笔记九动态规划-Yinode Blog

动态规划

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

动态规划

特征

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

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

最长公共子序列

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

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

动态规划 example

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

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

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

|S| 代表序列S的长度重点关注x y 的前缀 // 比如说一个序列X = 那么X3 = 其实就是把一个序列切成有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

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

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

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

|S| 代表序列S的长度重点关注x y 的前缀 // 比如说一个序列X = 那么X3 = 其实就是把一个序列切成有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的那个（你看找最优子结构特点来了）搜索 1. 找到匹配就输出 2. 没匹配就往箭头的方向去走

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

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

算法导论笔记九动态规划

TOC

动态规划

动态规划

特征

最长公共子序列

动态规划 example

特征

最长公共子序列

动态规划 example

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

FEATURED TAGS

动态规划

动态规划

特征

最长公共子序列

动态规划 example

特征

最长公共子序列

动态规划 example

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

FEATURED TAGS

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