动态规划(1)：基本思路以及步骤

本文主要是介绍动态规划(1)：基本思路以及步骤，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

基本思想

动态规划是针对一类求最优解的问题的算法，其核心是将一个问题分解成为若干个子问题（这里对应下文的子问题使用条件），部分类似于分治的思想（不懂得可以参考归并排序），通过求每一次的最优决策，来得到一个最优解。在这里最重要的就是子问题的思想。

另一种理解方式数是DP的核心是加法原理（下文的人人为我形递归）和乘法原理（下文的我为人人形递归）， 通过这两个原理， 在当状态的前有限多个状态中找到最优解来求得当前状态， 而对于前一个或者前几个状态采用同样的方法知道求出边界状态，这种方法最恶心的就是边界状态

在学会搜索之后，最简单入门DP的方法就是记忆话搜索，但是后来会发现大多数DP题目因为时间和内存的限制并不能使用递归（函数的递归调用会占用栈内存，另外函数的递归调用也将占用大量的时间）

子问题解决法的适用条件

需同时满足一下三点：

1.具有相同的子问题：我们必须保证我们分割成的子问题也能按照相同的方法分割成更小的自问题，并这些自问题的最终分割情况是可以解决的。

2.满足最优子结构：就是一个决策的子决策也是最优的

3.无后效性：这是DP中最重要的一点，他要求每个子问题的决策不能对后面其他未解决的问题产影响，如果产生就无法保证决策的最优性，这就是无后效性。往往需要我们找到一个合适的状态。
··这条非常重要
··这条非常重要
··这条非常重要
举个例子：我们在LIS中先求前M项的LIS，然后依次向后求，直到str.len，这就是因为我们在求前M项的过程中，对(M + 1)→(str.len)并无影响。消除后效性的例子等等会单开一片博客来讲。

常用的解题步骤

前两天刚刚被大牛虐过DP，姑妄言之：

第一步：确定子问题。在这一步重点是分析那些变量是随着问题规模的变小而变小的，那些变量与问题的规模无关。
第二步：确定状态：根据上面找到的子问题来给你分割的子问题限定状态
第三步：推到出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件，注意不要遗漏。
第四步：确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出，如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系，但是a(2)→a(1)不符合上述递推关系，我们就可以考虑用a(1)来倒推出a(2)，然后将递推的终点设置为a(2)）;
第五步：确定实现方式：这个依照个人习惯就像是01背包的两层for循环的顺序
第六步：确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存），优先队列、四边形不等式（优化时间）等等。