TOC
最长递增子序列
在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。
同样是一个经典的动态规划算法,与最长公共子序列相比，更加简单一些。
function lis(n) {
let len = n.length
let array = new Array(len).fill(1)
for (let i = 1; i < len; i++) {
for (let j = 0; j < i; j++) {
if (n[i] > n[j]) {
array[i] = Math.max(array[i], array[j] + 1)
}
}
}
return Math.max.apply(Math, array)
}
console.log(lis([0, 3, 4, 17, 2, 8, 6, 10, 11]))
值得一提的是LIS对于空间的占用是O(n)的，时间复杂度仍为O(n^2)
0-1背包问题
该问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。每个问题只能放入至多一次。
相比较于分数背包，01背包只能通过动态规划去解。
理解01背包解法的关键在于理解其最优子结构
假设我们拥有如下商品
| 物品 ID / 重量 | 价值 |
|---|---|
| 1 | 3 |
| 2 | 7 |
| 3 | 12 |
画一个表格来帮助我们理解整个流程
| 物品 ID / 剩余容量 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 3 | 3 | 3 | 3 |
| 2 | 0 | 3 | 7 | 10 | 10 | 10 |
| 3 | 0 | 3 | 7 | 12 | 15 | 19 |
事实上，解法就是按照这个表格进行一步步的填写内容，一个表格内部的项将会依赖其他已经填好的项目内容。
首先，我们需要明确的是 所谓01背包，其实就是一个物品，只有两种情况，拿 与 不拿！
- 首先，先填写我们目前只考虑拥有商品[0] 也就是整个表格的第一行,在拥有剩余空间i时的最大的价值
- 随后开始填写第二行，我们首先设置其初始值为 上一行的同列的内部值 这代表了在增加一个选择的情况下，相同金额，我们大不了不拿这个商品，这里就是针对不拿
接下来开始尝试增大这个价值，我们开始尝试回溯，也就是在上一行不拿当前物品的总量的情况下的价值，加上当前物品的价值(比较饶，确实很难解释，搭配代码看就很简单了)，去寻找一个相对于不拿的更高值。这里就是针对于拿，并且我要看拿了是不是能增加我当前的价值。
function knapsack(w, v, C) { let len = w.length let table = new Array(len).fill(new Array(C + 1).fill(0)) for (let j = 0; j <= C; j++) { table[0][j] = j >= w[0] ? v[0] : 0 } for (let i = 1; i < len; i++) { let cw = w[i] for (let j = 0; j <= C; j++) { table[i][j] = table[i - 1][j] if (j >= cw) { table[i][j] = Math.max(table[i][j], v[i] + table[i - 1][j - cw]) } } } return table[len - 1][C] }