作者：宋羽翔-ben | 来源：互联网 | 2023-10-14 15:14
第九章 动态规划
用表格法进行找最优方案
背包问题的最优方案
出去玩带东西的最优方案
对于字典查词的话，如果输入有误的话，比较俩个单词的相似性，可以用最长公共子串，不同的为零，相同的把左上方的值再加1导入当前的格子里，（为什么要引入最长公共子串呢及接着引出最长公共子序列呢），最长公共子序列，字母不同的话，就选择左边和上边格子里数值大的那个，相同的话，就是选完左边和上边格子里值大的然后再加1
动态规划不能解决的问题是彼此之间有依赖关系的，比如背包问题里，要偷走音箱也必须偷走CD机，这样的话会超重，
目录
9.1背包问题
9.2背包问题FAQ frequently asked question
9.3最长公共子串
9.4小结
9.1背包问题
偷东西的最终决策表格-----大事进行决策的时候也可以用表格法再加上权重
9.2背包问题FAQ
1.
多增加一个物品---照样可以用上述方法继续
行的排练顺序变了有影响吗？---没有
如果增加一个更小的商品，只有0.5磅，那就将表格的刻度画的更细一些，0.5，1，1.5等
可以偷商品的一部分吗？---动态规划没法处理，但是贪婪算法可以处理
2.其他例子，旅行最优化，换了约束条件，从背包的包的承重约束条件转为时间约束（只有俩天假期），但是还是一样的做法，表格
3.背包可能没装满----也就是说动态规划可能得到的不一定是最优解
4.动态规划可以解决把大问题分解为离散的子问题，而不能解决相互有依赖的子问题
9.3最长公共子串
引入个好玩的
想不出来怎么办，使用费曼算法：
把问题写下来
好好思考
把答案写下来
1.最长公共子串
对于一个词典，如果输入一个和原先要输入的单词只有一点点差别，词典怎么进行判断
画表格，不同的为零，相同的把左上方的值再加1导入当前的格子里，结果如下图
2.引入的问题背景是，如果有两个单词算出来的最长公共子串是一样的结果，那要怎么办呢？
比较其最长公共子序列，具体的算法是字母不同的话，就选择左边和上边格子里数值大的那个，相同的话，就是选完左边和上边格子里值大的然后再加1，结果如下
3.动态规划的实际应用
生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。
前面讨论了字符串的相似程度。
编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！
9.4小结
需要在给定约束条件下优化某种指标时，动态规划很有用。
问题可分解为离散子问题时，可使用动态规划来解决。
每种动态规划解决方案都涉及网格。
单元格中的值通常就是你要优化的值。
每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
没有放之四海皆准的计算动态规划解决方案的公式
京公网安备 11010802041100号