https://houbb.github.io/2020/01/23/data-struct-learn-07-base 算法概览

一. 动态规划

思想概念讲的特别好： https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp

计算机解决问题的方式就是穷举，算法的作用是让穷举更有效率！（来自网络名言）

动态规划解决斐波数列：对于递归的实现，其实动态规划的实现更好，会更节省内存。

function getNthNumOfFIBO(n) {
    const resultMap = { 0: 1, 1: 1 };
    if (n <= 1) {
        return resultMap[n];
    }
    for (let i = 2; i <= n; i++) {
        resultMap[i] = resultMap[i - 1] + resultMap[i - 2];
    }
    return resultMap[n];
}
console.log('fn(2): ', getNthNumOfFIBO(2));
console.log('fn(3): ', getNthNumOfFIBO(3));
console.log('fn(4): ', getNthNumOfFIBO(4));
console.log('fn(5): ', getNthNumOfFIBO(5));

求最长公共子串，这个也是利用动态规划做的吗，我写了一遍，感觉理解不了：
参考：https://blog.csdn.net/u010397369/article/details/38979077

// 最长公共字符串
// raven havoc => 'av'
function getMaxSubString(s1, s2) {
    const map = [];
    for (let i = 0; i < s1.length; i++) {
        let row = [];
        for (let j = 0; j < s2.length; j++) {
            if (s1[i] === s2[j]) {
                if ((i === 0) || (j === 0)) {
                    row.push(1);
                } else {
                    row.push(1 + map[i - 1][j - 1]);
                }
            } else {
                row.push(0);
            }
        }
        map.push(row);
    }
    return map;
}
const map = getMaxSubString('acbcbcef', 'abcbced');
for (let i = 0; i < map.length; i++) {
    console.log(map[i]);
}

来自司徒正美：https://segmentfault.com/a/1190000012864957 又看到了大神的文章，他曾经也迷茫，成名之后也还保持努力，非常有魅力的人物，36岁去世，缅怀。 — 他的文章有两个借鉴点：1）滚动数组节省空间 2）边界情况的处理

此外，还意外获取到一本书：《图解算法》看起来可以锻炼心智。

二. 背包问题

背包问题我是先看的书（《图解算法》），第一天没有看懂，就看别的了；第二天看懂了，还写出代码实现；第三天，决定写成文章，加深理解。总得来说，书上的语言也能讲得明白，但是仍然不是非常直白，所以有了这篇文章，去叙述下自己的理解，为自己后面复习也提供帮助，同样也能帮助其他人快速理解什么是背包问题，以及它的奥妙之处。

1. 问题描述

这个问题背景设置很有趣，我之前一直以为“背包问题”问题背景应该是爬山时往背包里塞装备，原来是在说偷东西，这让人很兴奋！

2. 思考过程

背包问题是动态规划，动态规划的实质是先解决小问题，然后用小问题的解，去解决大问题，and so on…
斐波数列的动态规划解决方式，就是典型的体现。
思想明了之后，接下来就是找突破口：背包问题，存在小问题的解去解决大问题吗？或者说大问题可以拆解为小问题吗？
我在刚刚阅读背包问题时，我的思维习惯是一维的：背包是4磅固定的，不断增加可以偷的商品数量，如果只能偷一件商品，最大的价值是多少；如果只能偷两件，最大的价值是多少。这样很符合直觉，但问题是：商品数量变得很多时，陷入大量排列组合中，人脑解决已经不切实际。
但是书中背包问题的解法，实际是二维的，这实际上在开始时很难理解。背包数量也 创造性 划分为1 2 3 4 磅分级，同时商品数量也是分为只能拿a，只能拿a b，只能拿a b c… 这样二维的划分，就形成了如下的网格：

解释和填写网格：

从行的角度看，从上到下：

第一行，被红色框住，对应于4列的单元格，每个单元格的意义：对于1磅、2磅、3磅和 4磅的四种背包，说明此时商场内只有吉他可以偷，其他物品没有；
第二行，被蓝色框住，说明此时只有吉他和音响可以偷；（单元格意义同上）
第三行，被绿色框住，说明此时只有 吉他音响 和 笔记__本电脑 可以偷。（单元格意义同上）

从列的角度看，从上到下：

第一行第一列，红色框，表示小偷有 1磅的背包，商场只有吉他可以偷，小偷有两种选择偷/不偷，背包有无奈装得下/装不下，前者可能是小偷有更好的选择，而背包却是硬性限制。综合来看，1磅的背包能装的下吉他，小偷此时只有吉他可以选择，本着“贼不走空”的原则，此时单元格去填上吉他的价格 1500。
第二行第一列，蓝色框，表示小偷有 1磅的背包，商场只有吉和音响他可以偷，相同道理，虽然音响更值钱但是单体超出背包总容量，所以，只能放弃，所以此时单元格去填上吉他的价格 1500。
第二行第二列，绿色框道理同上。

转折来了

第三行第三列，代表容量3磅的背包，此时可以偷吉他音响和 笔记__本电脑 ，单元格里填此时的最大值。我再填单元格时最大问题是会蒙圈，到底如何去填？其实是有相当明确的算法的：
当我们知道，我们有三种物品吉他音响和 笔记__本电脑 可以选择时，我们可以分为两类：选笔记本和不选笔记本，我们去分别计算满足背包容量限制和价值最大的原则。

其中不选笔记本，容量3磅的背包能获取的最大价值就在上方单元格里写着。我们唯一要计算的就是，选了笔记本之后价值是否有增加：我们可以看到，首先背包容量容许我们装入笔记本，而且价值 2000 > 1500。

关键点

这样算起来是最优解！
最后一个单元格才是我们要的问题答案，4磅容量的背包，三种物品可选，其正上方 3000 的单元格表明，没有笔记本电脑可选时的最大值。所以我们现在只需要计算如果要一定要选上笔记本时，价值是否会增加，对应的组合二是什么即可。笔记本电脑 3磅，4磅容量的背包还剩 1 磅，并且这一磅只能选择两样物品（吉他和音响），所以第二行第一列的1500 正好满足标准，已经帮我们计算好了，所以我们找到了最优解！

3. 代码实现

实现后发现代码量还是蛮多的，还有不少边界需要处理，以及条件判断。

// 背包问题：系统化穷举
const goodsArray = [
    [10, 3, 'water'], [3, 1, 'book'], [9, 2, 'food'], [5, 2, 'jacket'], [6, 1, 'camera']
];
const containerWeightArray = [1, 2, 3, 4, 5, 6];
console.log(getResult(goodsArray, containerWeightArray))
function getResult(goodsArray, containerWeightArray) {
    const resultForm = [];
    for (let i = 0; i < goodsArray.length; i++) {
        let lineInfo = [];
        for (let j = 0; j < containerWeightArray.length; j++) {
            const containerWeight = containerWeightArray[j];
            const [goodsValue, goodsWeight, goodsName] = goodsArray[i];
            let leftWeight = containerWeight - goodsWeight;
            let preMaxValue = 0;
            let preMaxWeight = 0;
            let preMaxGoods = [];
            if (i > 0) {
                preMaxValue = resultForm[i - 1][j][0];
                preMaxWeight = resultForm[i - 1][j][1];
                preMaxGoods = resultForm[i - 1][j][2];
            }
            let subMaxValue = 0;
            let subMaxWeight = 0;
            let subMaxGoods = [];
            if ((i > 0) && (j > 0)) { // 把边的单元格没有 子问题 的最优解
                if (leftWeight >= 0) {
                    let subMaxItemIndex = containerWeightArray.findIndex(i => i === leftWeight);
                    if (subMaxItemIndex !== -1) {
                        let subMaxItem = resultForm[i - 1][subMaxItemIndex];
                        subMaxValue = subMaxItem[0];
                        subMaxWeight = subMaxItem[1];
                        subMaxGoods = subMaxItem[2];
                    }
                }
            }
            let targetMaxValue = 0;
            let targetMaxWeight = 0;
            let targetMaxGoods = [];
            if ((leftWeight >= 0) && ((subMaxValue + goodsValue) > preMaxValue)) { // 可以不考虑 else 的解释，只考虑，假如 背包可以装得下当前物品，且价值增加，则更新此单元格，否则，和之前一样
                targetMaxValue = subMaxValue + goodsValue;
                targetMaxWeight = subMaxWeight + goodsWeight;
                targetMaxGoods = subMaxGoods.slice(0);
                targetMaxGoods.push(goodsName);
            } else { // 包含两种情况 1）leftWeight < 0 背包剩余空间装不下  2）leftWeight >= 0 && (subMaxValue + goodsValue) <= preMaxValue 背包剩余空间装得下，但是价值没有增长
                targetMaxValue = preMaxValue;
                targetMaxWeight = preMaxWeight;
                targetMaxGoods = preMaxGoods;            
            }
            lineInfo.push([targetMaxValue, targetMaxWeight, targetMaxGoods]);
        }
        resultForm.push(lineInfo);
    }
    return resultForm;
}

三、寻找最长递增子序列
这个算法在 vue 3.0 里的 diff 被用到：最长递增子序列减少移动操作次数！

// 输入：nums = [10,9,2,5,3,7,101,18]
// 输出：4
function test(arr) { // 部分完成
  const innerMap = new Map();
  for (let i = (arr.length - 1); i >= 0; i--) {
    let item = arr[i];
    if (innerMap.size === 0) {
      innerMap.set(item, 1);
    } else {
      for (let [key, value] of innerMap) {
        if (item < key) {
          innerMap.set(item, value + 1);
        } else {
          innerMap.set(item, value);
        }
      }
    }
  }
  return innerMap;
}
// 分析过程：倒着分析
// arr.length - 1  -2
// 18  101    7       3        5        2      9       10
// 1   1      1+1=2   2+1=3    1+2=3    3+1=4  1+1=2   1+1=2
// 分析结果：有四种序列可以满足要求
// 2 5 7 18/101
// 2 3 7 18/101

算法和代码能力

算法准备 - 动态规划

一. 动态规划

二. 背包问题

1. 问题描述

2. 思考过程

3. 代码实现