前言
学习python数据结构与算法，学习常用的算法，
b站学习链接
88.动态规划介绍
动态规划在基因测序、基因比对、hmm 有应用场景。
从斐波那契数列看动态规划
练习： 使用递归和非递归的方法来求解斐波那契数列。
这种非递归求斐波那契数，可以看成是一个动态规划思想，每次都会把重复子问题的答案存起来。
89.钢条切割问题
长度为n的一共有n-1口可以切，每一口可以选择切或者不切，所以有2^n-1种不同的方法。
r[i]那行是长度为i时，最多买的钱。可以这样考虑，在长度为2时，可以选择切成1和1 或者不切，不切最大利润是5，切了后最大利润是2，把最大利润存到r[2]下，当r[3]时，可以不切或者切成1和2（不考虑切成1、1、1，因为在r[2]中已经考虑过1和1 的利润没2大），选择最大的8存放在r[3]中，按照这样的思想，比方说看r[9],看不切或1和8或2和7或3和6或4和5，选择最大的放到r[9],
先看1和8，1+22
2和7，5+18
3和6，8+17
4和5，10+13
于是我们可以推出递推式，不切和切一刀之后最大值就是利润最大。此时从左边往右边切和从右边往左切是一样的，但我们还是考虑了切成5和4，切成6和3的情况。
我们可以将求解规模为n的原问题划分成规模更小的子问题：完成一次切割后，可以将产生的两端钢条看成两个独立的钢条切割问题，
这就叫最优子结构，把9的最大=3最大+6最大。
此时可以得出以上的递推式，不过还可以再进行简化，以上是不切和切一次的不同位置来构成的递推式。
这样还是切9， 左边一部分是不切的，所以价值是原来不切的价值
1和8，1+20
2和7，5+18
3和6，8+17
4和5，9+13
5和4，10+10
6和3，17+8
7和2，17+5
8和1，20+1
25还是最大，为什么可以这样做呢？因为现在最大是3和6 实则是3和6，但假设如果最大是23 那就是2和2和2和3，2没切，后面的7切成了三段，或者假设说是4和5，4没切，5切成2和3，那么就是说，这样左边没切，右边切，所有的情况还是都能列举，之前的方法有重复了，所以可以这样简化。
90.钢条切割问题：自顶向下实现
对照上面的公式写出以下两种实现，第二种简化的方法，少了一次递归，时间上少了很多。
将p改成p = [0,1,5,8,9,10,17,17,20,24,30,31,33,35,36,40,41,42,45,46,50]，长度改大，计算最大的时间也变慢了。
因为递归算法由于重复求解相同子问题，效率极低，随着长度越大，求解速度会变慢
因为这是用了自顶向下递归实现，为何自顶向下递归的效率会这么差？
时间复杂度为O(2^n),如果n越大，就会造成指数爆炸。
求f(4),会重复求许多相同的问题。
动态规划的思想：每个问题只求解一次，保存求解结果
之后需要此问题时，只需要查找并保存结果。
91.钢条切割问题：自底向上实现
动态规划就是自底向上实现，每次都把最好的存起来，调用时直接取出来，不用再算。
按照第二种简化的方法写。
时间上比递归的方法快很多，时间复杂度为O(n^2)
92.钢条切割问题：重构解
如何修改动态规划算法，使其不仅输出最优解，还输出最优切割方案？
对每个问题，保存切割一次时左切切下的长度，s[i]为保存的当前最优利润时，左切下的长度
max()的话就不知道里面左边不切割的长度是多少，所以要换成以下写法
实际上这样把每次切出来的长度列出来，有个专有的名词叫路径带回
什么问题可以用动态规划方法？涉及到最大，最小，最优时
实际上，贪心算法是动态规划一个特例，贪心能解动态也能解，贪心不能解，动态也能解。
可以先从递归的思想想问题，如果递归能解就意味着动态规划能解。
93.最长公共子序列
首先要找到递推式或者说是最优子结构。
我们发现这样一个规律，如果两个字符串的最后一个字符不相等，比如说“ABCBDAB”和“BDCABA”这两个字符串找最长公共子序列。我们先看最后一个字符，不一样，那么我们可以等同于“ABCBDAB”和“BDCAB”中找最长公共子序列，或者“ABCBDA”和“BDCABA”中找，两者中哪个最长就是最长的公共子序列。如果最后一个字符一样，比如“ABCBDA”和“BDCABA”，那么最长的公共子序列就等于“ABCBD”和“BDCAB”的最长公共子序列 +1(因为最后一个字符相等)。
就得出如下定理：
安照这个图得出，空字符时都为0，如果末尾字符相等，那就取上面格子和下面格子的最大值，如果不相等，就取左上角一个格子的值+1。（从左上角过来的值代表匹配）
94.最长公共子序列：实现
首先求最长公共子序列的长度
再利用回溯法得出，这个最长的子序列的字符是多少
这种做法只能求得一个，如果 elif c[i-1][j] > c[i][j-1]: 改成 >= 则答案是BCBA，这两个都是最长公共子序列，所以都是对的。
存的路径如下。
文章来源：https://www.toymoban.com/news/detail-407816.html
总结
学习了动态规划算法。
文章来源地址https://www.toymoban.com/news/detail-407816.html
到了这里，关于【零基础】学python数据结构与算法笔记14-动态规划的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
