动态规划问题

动态规划（英语：Dynamic programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划的基本思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

---

背包问题（Knapsack problem）
一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

关于各种背包问题的讲解详见：背包问题九讲

这里给出01背包问题和完全背包问题的JavaScript实现
另外，“换零钱问题”也是背包问题中的一种。

01背包问题
有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

这是最基础的背包问题。
特点：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即F [i, v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

【“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只和前i − 1件物品相关的问题。如果不放第i件物品，那么问题就转化为“前i − 1件物品放入容量为v的背包中”，价值为F [i − 1, v]；如果放第i件物品，那么问题就转化为“前i − 1件物品放入剩下的容量为v − Ci的背包中”，此时能获得的最大价值就是F [i − 1, v − Ci]再加上通过放入第i件物品获得的价值Wi。】

let dp = new Array()
for (let i = 0; i < 1000; i++) {
  dp[i] = new Array()
  for (let j = 0; j < 1000; j++) {
    dp[i][j] = 0
  }
}

function pack(n, capacity, costs, values) {
  if (n < 0 || capacity < 0) return -1
  if (n === 0 || capacity === 0) return 0
  
  for (let i = 0; i <= n; ++i) {
    for (let j = 0; j <= capacity; ++j) {
      if (i > 0 && j >= costs[i - 1]) {
        dp[i][j] = Math.max(dp[i - 1][j], 
                    dp[i - 1][j - costs[i - 1]] + values[i - 1])
      }
    }
  }

  return dp[n][capacity]
}

console.log(pack(4, 10, [1, 3, 4, 5], 
                        [3, 6, 2, 8]))
// 输出
17

完全背包问题
有N种物品和一个容量为V 的背包，每种物品都有无限件可用。放入第i种物品的耗费的空间是Ci，得到的价值是Wi。求解：将哪些物品装入背包，可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……直至取⌊V /Ci⌋件等很多种。

如果仍然按照解01背包时的思路，令F [i, v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：

这跟01背包问题一样有O(V N)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态F [i, v]的时间是O(v / Ci)，总的复杂度可以认为是O(NV Σ(v / Ci))，是比较大的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是要试图改进这个复杂度。

最少换零钱问题
如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够22元？求出最少硬币数。

let dp = [1]

function MinRCIter(aim, faceValueArr) {
  if (aim < 0) { return 100000000 }
  if (aim === 0) { return 0 }

  if (dp[aim]) {
    return dp[aim]
  }

  let localMin = 100000000

  for (let i = 0; i < faceValueArr.length; i++) {
    if (aim === faceValueArr[i]) {
      return 1
    }

    let rest = MinRCIter(aim - faceValueArr[i], faceValueArr)
    localMin = Math.min(localMin, rest + 1)
  }

  dp[aim] = localMin
  return dp[aim]
}

function MinReplaceChange(aim, arr) {
  console.log('Least: ' + MinRCIter(aim, arr))
}

// 测试
MinReplaceChange(22, [1, 3, 5])
// 输出
Least: 6

---

最长递增子序列（longest increasing subsequence）问题
在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。

给定一个长度为n的数组a[0], a[1], a[2]..., a[n-1]，找出一个最长的单调递增子序列（注：递增的意思是对于任意的i < j，都满足a[i] < a[j]，此外子序列的意思是不要求连续，顺序不乱即可）。
例如：给定一个长度为6的数组: [5， 6， 7， 1， 2， 8]，则其最长的单调递增子序列为[5，6，7，8]，长度为4。

用dp[i]表示以i结尾的子序列中LIS的长度。然后用dp[j] (0 <= j < i)来表示在i之前的LIS的长度。然后我们可以看到，只有当a[i] > a[j]的时候，我们需要进行判断，是否将a[i]加入到dp[j]当中。

为了保证我们每次加入都是得到一个最优的LIS，有两点需要注意：（1）每一次，a[i]都应当加入最大的那个dp[j]，保证局部性质最优，也就是我们需要找到max(dp[j] (0 <= j < i))；（2）每一次加入之后，我们都应当更新dp[j]的值，显然，dp[i] = dp[j] + 1。
如果写成递推公式，我们可以得到dp[i] = max(dp[j] (0 <= j < i)) + (a[i] > a[j] ? 1 : 0)。

JavaScript实现
【时间复杂度：O(n ^ 2)】

let dp = [1]
let pre = [null]

function lisIter(endWith, listArr) {
  if (dp[endWith]) { 
    return dp[endWith] 
  }

  let localMaxLen = 1
  for (let i = 0; i < endWith; i++) {
    if (listArr[i] < listArr[endWith]) {
      if (localMaxLen < lisIter(i, listArr) + 1) {
        localMaxLen = lisIter(i, listArr) + 1
        pre[endWith] = i
      }
    }
  }
  
  dp[endWith] = localMaxLen
  return dp[endWith]
}


function LIS(arr) {
  for (let i = 0; i < arr.length; i++) {
    lisIter(i, arr)
  }

  let answer = -1
  let lastNode = -1
  for (let i = 0; i < dp.length; i++) {
    if (answer < dp[i]) {
      answer = dp[i]
      lastNode = i
    }
  }

  const seq = []
  do {
    seq.unshift(arr[lastNode])
    lastNode = pre[lastNode]
  } while(lastNode !== null)

  console.log('length: ' + answer)
  console.log('list: ' + seq)
}

// 测试
LIS([3, 5, 8, 2, 9, 10, 4])
// 输出
length: 5
list: 3,5,8,9,10

---

斐波那契数列
详见上一篇《斐波那契数列及其优化》。

---

汉诺塔问题
详见《汉诺塔问题》

---