『算法』『数据结构』|『算法』『数据结构』浅谈动态规划算法，理解程序员必懂必会的计算机常见算法—

基本认识动态规划（ dynamic programming ）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。
基本思想与原理动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。
适用的问题那么什么样的问题适合用动态规划的方法来解决呢？
适合用动态规划来解决的问题，都具有下面三个特点：最优化原理、无后效性、有重叠子问题。
（1）最优化原理：
一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。简而言之，一个问题满足最优化原理又称其具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：
即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。一般情况下，树形分支结构由根到叶方向的决策都是满足无后效性的。
（3）有重叠子问题：
即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）。
求解的步骤与模板这类问题的求解步骤通常如下：
初始状态→│决策1│→│决策2│→…→│决策n│→结束状态
一、确定动态规划的三要素（状态、状态转移方程、边界条件）（1）划分状态与确定状态和状态变量（状态）：
思考状态可以先尝试“题目问什么，就把什么设置为状态”。然后考虑“状态如何转移”，如果“状态转移方程”不容易得到，尝试修改定义，目的仍然是为了方便得到“状态转移方程”。
状态划分是指，按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的。
确定状态和状态变量是指：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性。
（2）确定决策并写出状态转移方程（重点、核心）：
状态转移方程是非常重要的，是动态规划的核心，也是难点，起到承上启下的作用。状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程。
归纳“状态转移方程”是一个很灵活的事情，得具体问题具体分析，除了掌握经典的动态规划问题以外，还需要多做题。如果是针对面试，请自行把握难度，我个人觉得掌握常见问题的动态规划解法，明白动态规划的本质就是打表格，从一个小规模问题出发，逐步得到大问题的解，并记录过程。动态规划依然是“空间换时间”思想的体现。
（3）边界条件（初始化）：
状态转移方程是一个递推式，因此需要找到递推终止的条件，即边界条件，这个过程又称为初始化。
二、后续完善工作（1）思考输出：
输出有些时候是最后一个状态，有些时候可能会综合所有计算过的状态。
（2）思考状态压缩：
“状态压缩”会使得代码难于理解，初学的时候可以不一步到位。先把代码写正确，然后再思考状态压缩。
状态压缩在有一种情况下是很有必要的，那就是状态空间非常庞大的时候（处理海量数据），此时空间不够用，就必须状态压缩。

文章图片
这里借用Leetcode上一位大佬的图片来帮助理解引例部分 【『算法』『数据结构』|『算法』『数据结构』浅谈动态规划算法，理解程序员必懂必会的计算机常见算法——动态规划】爬楼梯问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
解题思路
假定n=10,首先考虑最后一步的情况,要么从第九级台阶再走一级到第十级,要么从第八级台阶走两级到第十级,因而,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始.也就是说已知从地面到第八级台阶一共有X种走法,从地面到第九级台阶一共有Y种走法,那么从地面到第十级台阶一共有X+Y种走法。
即F(10)=F(9)+F(8)
分析到这里,动态规划的三要素出来了：
状态：
例如，F(10)的最优子结构即F(9)和F(8)，依此类推。
状态转移方程：
F(n)=F(n-1)+F(n-2)
边界条件：
F(1)=1,F(2)=2
实战部分 最长回文字符串问题

文章图片
在这里插入图片描述
解题思路
这道题比较烦人的是判断回文子串。因此需要一种能够快速判断原字符串的所有子串是否是回文子串的方法，于是想到了“动态规划”。
“动态规划”最关键的步骤是想清楚“状态如何转移”，事实上，“回文”是天然具有“状态转移”性质的：一个回文去掉两头以后，剩下的部分依然是回文（这里暂不讨论边界）。
依然从回文串的定义展开讨论：
1、如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
2、如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
（1）如果里面的子串是回文，整体就是回文串；
（2）如果里面的子串不是回文串，整体就不是回文串。即在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。因此可以把“状态”定义为原字符串的一个子串是否为回文子串。
第 1 步（状态）：
定义状态dp[i][j] 表示子串 s[i, j] 是否为回文子串。
第 2 步（状态转移方程）：
思考状态转移方程这一步在做分类讨论（根据头尾字符是否相等），根据上面的分析得到： dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]分析这个状态转移方程：
（1）“动态规划”事实上是在填一张二维表格，i 和 j 的关系是 i <= j ，因此，只需要填这张表的上半部分；
（2）看到 dp[i + 1][j - 1] 就得考虑边界情况。边界条件是：表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。这个结论很显然：当子串 s[i, j] 的长度等于 2 或者等于 3 的时候，我其实只需要判断一下头尾两个字符是否相等就可以直接下结论了。如果子串 s[i + 1, j - 1] 只有 1 个字符，即去掉两头，剩下中间部分只有 11 个字符，当然是回文；如果子串 s[i + 1, j - 1] 为空串，那么子串 s[i, j] 一定是回文子串。因此，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下结论，dp[i][j] = true，否则才执行状态转移。 (如果看不明白，可以对照代码理解)
第 3 步(边界条件）：
考虑初始化初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 1，即 dp[i][i] = 1 。事实上，初始化的部分都可以省去。因为只有一个字符的时候一定是回文，dp[i][i] 根本不会被其它状态值所参考。
第 4 步（思考输出）：
考虑输出只要一得到 dp[i][j] = true，就记录子串的长度和起始位置，没有必要截取，因为截取字符串也要消耗性能，记录此时的回文子串的“起始位置”和“回文长度”即可。
第 5 步（思考状态压缩）：
考虑状态是否可以压缩因为在填表的过程中，只参考了左下方的数值。事实上可以压缩，但会增加一些判断语句，增加代码编写和理解的难度，丢失可读性。在这里不做状态压缩。
下面是编码的时候要注意的事项：
总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果。思路是：
1、在子串右边界 j 逐渐扩大的过程中，枚举左边界可能出现的位置；
2、左边界枚举的时候可以从小到大，也可以从大到小。这两版代码的差别仅在内层循环，希望大家能够自己动手，画一下表格，思考为什么这两种代码都是可行的，相信会对“动态规划”作为一种“表格法”有一个更好的理解。
下面附上Python3的题解代码

class Solution: def longestPalindrome(self, s: str) -> str: size = len(s) if size < 2: return sdp = [[False for _ in range(size)] for _ in range(size)]max_len = 1 start = 0for i in range(size): dp[i][i] = Truefor j in range(1, size): for i in range(0, j): if s[i] == s[j]: if j - i < 3: dp[i][j] = True else: dp[i][j] = dp[i + 1][j - 1] else: dp[i][j] = Falseif dp[i][j]: cur_len = j - i + 1 if cur_len > max_len: max_len = cur_len start = i return s[start:start + max_len]

趁热打铁刷题练习部分（持续更新）以下是LeetCode题库中一些用到动态规划的经典例题的题目及解析，有题干，有题解代码、有解题思路（持续更新）：
No.5.最长回文子串：
https://blog.csdn.net/LanXiu_/article/details/104026241
No.32.最长有效括号：
https://blog.csdn.net/LanXiu_/article/details/104161616
No.44.通配符匹配：
https://blog.csdn.net/LanXiu_/article/details/104177349