动态规划基础入门模板总结_动态规划基础模板

动态规划题目的特点

动态规划的题目没有固定的样式，要解决动态规划题目首先要知道哪些题目可以使用动态规划求解，最基本的分类有以下三种。

1.计数题

这种题目往往要求给出符合某种条件的解的数量，类似的题目有：
---->有多少种方式走到右下角
---->有多少种方式选出k个数使得和为sum

2.求最大最小值

顾名思义，就是题目要求你给出一个最大值或最小值，不论是花费的最小值还是其他类型的最大最小值，都在这个范围内，类似的题目有：
---->从左上角走到右下角路径的最大数字和
---->最长上升子序列长度

3.求存在性

存在性题目一般要求返回boolean类型的值，题目会问我们是否存在一个解符合条件，此类问题有：
---->取石子游戏，先手是否必胜
---->能不能选取k个数，使他们的和为sum

动态规划解题模板

通常来说，动态规划完整的解题思路包括四个组成部分：确定状态、状态转移方程、初始条件和边界条件、计算顺序。
以下以一例解说：
题目：现有2元，5元，7元三种不同规格的硬币，数量不限，从中选出k个硬币，使得能组成n元，求k的最小值。（原题中硬币的规格 为传入的一个数组，此处取为[2,5,7]便于理解）

1.确定状态

解开动态规划需要设置一个数组，确定每个元素代表什么意思。
确定状态需要两个意识：“最后一步”、“子问题”。

1.1最后一步：即为最优策略中的最后一步决策。

在例题中，我们可以很轻易地得到，最后一步即为最后一枚硬币A_k。

1.2子问题：去掉最后一步之后，剩下待处理的问题与原问题相似。

去掉最后一步，剩下的子问题题为：选出k-1个硬币，使得能组成n-A_k元，求k-1的最小值。
而这个子问题依然可以继续划分子问题，直到最后需要组成0元。.

2.状态转移方程

我们在第一步确定状态中已经得到了“最后一步”与“子问题”，在第二步按照“最后一步”与“子问题”即可写出动态转移方程。

那么我们知道了最后一步与子问题之后，怎么写出状态转移方程。我们要解决n元的组合问题，不妨设最小的硬币数为f(n)，那么n在子问题中可以分解为0,1,2,…,n总共n个数，在写代码时可以设一个长度为n+1的数组来保存。

以例题为例，我们知道了最后一步是最后一枚硬币，但不知道到底是2元、5元还是7元，那么就应该列出所有情况:2元、5元和7元。

对应的子问题即为f(n-2)、f(n-5)和f(n-7)。

最后，我们再回到原问题上，因为要求最小值，那么得到
f(n) = min{f(n-2)+1,f(n-5)+1,f(n-7)+1}

这里为什么要 加一 ，是因为对于原问题来说，子问题到原问题需要多加一枚硬币，这很好理解。就是说，到子问题需要k枚硬币的话，那么从这个子问题到原问题硬币数必须加一。

为什么不用递归： 使用递归时，不同的分支无法检测其他分支中的运算，难免造成重复计算，当数值较大时，所消耗的时间空间会指数级上升，有时甚至会造成StackOverFlow（SOF），如下图：

f(20)与f(18)都计算了多次，非常影响效率。

3.初始条件和边界条件

3.1初始条件

初始条件是考虑刚开始时某些部分的初始值是否要设置以及设置为多少

我们首先可以知道要组成0元需要0枚硬币，可以直接设 f(0) = 0;
其他的初始条件还有不能组成硬币的1元，3元等，不需要过多设置，否则有些难以考虑到的值难免疏漏，可以把这一部分交给边界条件实现。
而f(2) f(5) f(7)这些应该交给循环来计算得出，没有必要一定自己设定初始值。

3.2边界条件

边界条件考虑的是 什么时候停止。

很显然，当我们运算时难免得到n为负数的情况，那么我们在求最小值的问题中，应该将n为负数的情况设置为MAX_VALUE。

现在再看正数中不能实现数，比如f(1)
f(1) = min{f(-1)+1,f(-4)+1,f(-6)+1}
因为三个数都是负数，则可以得到全为无限大，那么f(1)可以直接得到值为无限大。（在程序中我们应该注意MAX_VALUE经过加一后溢出的事实，所以实际代码应有针对性改进，除此之外还有数组下标不能为负数）

4.计算顺序

通常情况下动态规划为从左到右从上到下（从上到下为二维数组考虑，一般不出现三维才能求解的情况，至今还未遇到过）。

当我们分析计算顺序时，只需要考虑一个问题：计算f[n]时，调用的数值是否全都经过计算
如：f(n) = min{f(n-2)+1,f(n-5)+1,f(n-7)+1}，当计算f(n)时要保证其中所有的数都计算过，则应该从左往右遍历

小结

该博客面向初学者，其中有不足之处还请指正。

在真实刷题过程中，还有一些特别的情况存在，比如：不必初始化、不必额外设置边界条件（数组遍历结束即结束）、状态转移方程难以表示（因为本人没有系统地学习此类相关的表达式格式，有一部分不会用状态转移方程表示，比如遍历数组内所有的值得到一个符合条件的值即返回，这种表达式是真的不会写，但是写代码能表示出来也是可以的）。

对于算法题中各类复杂的题目，还是需要融会贯通之后才有足够的能力解出，不建议照着模板写题，最好的方式还是学习时间和实践代码区分开来，有时间的可以去各大刷题网站写一下简单的动态规划，看完这篇博客应该是简单难度的题都能A了。