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，所有文档和源码会同步更新
