算法学习——DP

20170904开端

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

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)

题目 leetcode链接

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

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实现，地址在github，所有文档和源码会同步更新