动态规划
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
背包问题
简单算法, 书中一开始是通过排列组合的方式, 但是速度有些慢, 时间复杂度为 O(n2)
引入动态规划, 将背包问题绘制成表格
[图片上传失败...(image-a29e02-1528622649240)]
音响(3000美元、 4磅)、 笔记本电脑(2000美元、3磅)、 吉他(1500美元、1磅)
最终结果, 将吉他和笔记本电脑放入背包时价值最高, 为 3500 美元
[图片上传失败...(image-65950a-1528622649240)]
最长公共子串
引入一个例子。 假设你管理着网站 dictionary.com。 用户在该
网站输入单词时, 你需要给出其定义。
但用户拼错了, 你必须要猜测他原本要输入的是什么单词。 例如, Alex 想查单词fish, 但不小心输入了hish。 在你的字典中, 根本就没有这样的单词, 但有几个类似的单词。
同样绘制表格, 这其实是求最长公共子串
image
最长公共序列
[图片上传失败...(image-ce6269-1528622649240)]
image
伪代码
if word_a[i] == word_b[j]: # 两个字母相同
cell[i][j] = cell[i-1][j-1] + 1
else: # 两个字母不同
cell[i][j] = max(cell[i-j][j], cell[i][j-1)
小结
书上的例子还是比较好理解的, 实际中的那些题目可能就够呛了
最后附上小灰漫解动态规划: https://juejin.im/post/5a29d52cf265da43333e4da7
