20170904开端

今天工作任务比较轻，工作之余想要重新学习算法。于是准备从DP开始，进行一次学习。所有的概念和问题从和获取。

DP Set 1 (Overlapping Subproblems Property)

重复子问题

像分治法一样，DP解决的问题都是可以分解成很多子问题的。但不同的是，DP解决的问题一定是有重复计算部分的。

例如

以fib数列举例，简单的递归实现没有避免重复子问题，导致计算过程中重复计算的部分很大，从而降低效率。

function fib (n) {  if (n <= 1) return n  return fib(n - 1) + fib(n - 2)}

fib(5)                     /             \               fib(4)                fib(3)             /      \                /     \         fib(3)      fib(2)         fib(2)    fib(1)        /     \        /    \       /    \  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)  /    \fib(1) fib(0)

优化重复子问题

记忆化

这是一种自顶向下的方法

// Memoization (Top Down)function fibWithMem (n) {  var mem = []  for (var i = 0; i < n + 1; ++i) {    mem[i] = null  }  function _fib (m) {    if (mem[m] === null) {      mem[m] = m <= 1 ? m : _fib(m - 1) + _fib(m - 2)    }    return mem[m]  }  return _fib(n)}

通过预先定义好空数组mem，然后不断更新mem，借助mem进行重复子问题的优化。

制表

这是一种自底向上的方法

// Tabulation (Bottom Up)function fibWithTab (n) {  var tab = [0, 1]  if (n <= 1) return tab[n]  for (var i = 2; i <= n; ++i) {    tab[i] = tab[i - 1] + tab[i - 2]  }  return tab[n]}

通过预先定义好基线条件的数组tab，在运行过程中，不断利用tab计算下一个目标值，达到重复子问题的优化目的，并且去掉了递归。

DP Set 2 (Optimal Substructure Property)

• 最短路径问题可以用DP解决，因为其具有最优子结构的特性。

• 最长路径问题不能用DP解决，因为其不具有最优子结构的特性。

DP Set 3 (Longest Increasing Subsequence)

题目

解法一 利用该问题的最优子结构进行求解

function lis (arr, n) {  var curMax = 1  function _lis (arr, n) {    if (n <= 1) return n    var maxHere = 1    var res = 1    for (var i = 1; i < n; i++) {      res = _lis(arr, i)      if (arr[i - 1] < arr[n - 1] && res + 1 > maxHere) maxHere += 1    }    if (curMax < maxHere) curMax = maxHere    return maxHere  }  _lis(arr, n)  return curMax}

上述解法会超时，因为只利用到了最优子结构的特性，而没有进行重复子问题的优化。对于一个长度为4的测试数据而言，调用的结构图如下。

lis(4)        /        |           lis(3)    lis(2)   lis(1)     /           /   lis(2) lis(1) lis(1)   /lis(1)

利用制表，改进解法一

function lisWithTap (arr, n) {  var tab = []  for (var m = 0; m < n; m++) {    tab[m] = 1  }  for (var i = 1; i < n; i++) {    for (var j = 0; j < i; j++) {      if (arr[j] < arr[i] && tab[i] < tab[j] + 1) {        tab[i] = tab[j] + 1      }    }  }  return Math.max.apply(null, tab)}

通过制表，消去了递归，并且避免了重复计算相同的子问题。

进一步思考

• DP解法的时间复杂度为O(n^2)

• 时间复杂度可以被优化为O(nlogn)

• 对问题进行分析，采用维护LIS的思想

function lisFast (arr, n) {  if (n <= 1) return n  var tail = new Array(n)  tail.fill(0)  var length = 1  tail[0] = arr[0]  for (var i = 1; i < n; i++) {    if (arr[i] < tail[0]) {      tail[0] = arr[i]    } else if (arr[i] > tail[length - 1]) {      tail[length] = arr[i]      length += 1    } else {      tail[findCeilIndex(arr, 0, length - 1, arr[i])] = arr[i]    }  }  return length}function findCeilIndex (arr, left, right, val) {  var l = left  var r = right  while (r - l > 1) {    var mid = Math.floor(l + (r - l) / 2)    if (arr[mid] >= val) {      r = mid    } else {      l = mid    }  }  return r}

以上所有代码全部以JS实现，同时还有cpp实现，地址在，所有文档和源码会同步更新