背包问题
- 继续上面贪婪算法的背包问题场景
简单算法
- 尝试各种可能的组合，并找出价值最高的组合
- 3 件商品就会计算 8 个组合，4 件商品就会计算 16 个集合
- 这就是前面说到的集合覆盖问题，每增加一件商品，需要计算的都要翻倍
- 这种简单算法的运行时是 O（2 ~n）2 的 n 次方
- 所以一多，这种算法就行不通，之前就用了近似算法
动态规划
- 动态规划就是背包问题的最优解
- 动态规划的本质是先解决子问题，再逐步解决大问题
- 每个动态规划都从一个网格开始
- 每个子问题都是离散的，不相互依赖才可以
最长公共子串
- 单元格中的值通常就是你要优化的值。在前面背包问题中，单元格中的值就是你要优化的值。
- 每个单元格都是子问题
场景
- 用户输错了单词，本来想输 fish，但是输了 hish
- 假设与 hish 类似的词只有两个（实际上上千个），fish 和 vista，怎么确定是哪一个（哪个单词和它更像）
- hish 和 fish 都包含的最长公共子串是 ish，用网格来算
- hish 和 vista 都包含的最长公共子串是 is，用网格来算
- 因为 fish 的最长公共子串是 3 个，因此用户应该是想输入它
最长公共子序列
- 与最长公共子串计算方式不一样
动态规划应用
- git diff 比较文件差异
- 生物学家使用最长公共子序列来确定 dna 的相似性