DP算法（动态规划算法）

前几天做leetcode的算法题很多题都提到了动态规划算法，那么什么是动态规划算法，它是什么样的思想，适用于什么场景，就是我们今天的主题。

首先我们提出所有与动态规划有关的算法文章中都会提出的观点：　将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

什么都不了解的话看到这句话是懵逼的，我们也先略过，等看完整篇文章再回过头来看一看这个观点。

下面正式开始。

首先我们来看这个译名，动态规划算法。这里的动态指代的是递推的思想，算法在实现的过程中是动态延伸的，而不是提前控制的。规划指的是需要我们给出动态延伸的方法和方向。

这两个就是算法的问题点。

我们来看看这其中规划的展现部分，规划展现在情况分类上，我们只有三种钱币，所以会要求实现f[n]中的n要大于某一个规定值才是可取的，要10元时候我们不可以取出11元，所以在这部分要进行单独判断。

再说动态部分，显然，f[4],f[10],f[14]是我们需要单独去计算的，那么如何计算呢，就需要他们动态的去递推下一步如何计算。

来看看这个式子：f(n)=min{f(n-1),f(n-5),f(n-11)}+1

显然f(n)直接由后三个值决定，我们只要算出这三个值即可，而这三个值又由同样式的更小值决定，只要得出更小值，甚至最小值，我们就可以推导出f(n)。

实际上是一种冗余信息的反向筛查算法，是暴力枚举的简化。

来看看使用dp算法的要求。

这也同时揭示了我一开始写的那句话，大问题由小问题累积而成，是必要的。

实际的例子我用前两天的几道动态规划的算法题来举例。

一道一道来：

1.delete operation for two strings

java：

这里的特殊点在于需要每一步都比较，也就是[i-1][j]与[j][i-1]，而不是[i][j]；

5就不说了，是标准的最长公共子序列问题，上一道问题的缩减版，注意的是由于要求最长长度，所以用的是max。

6.​​regular expression matching​​

这道题考虑到一个问题点就是在特殊情况下的判断问题，我们抛开matches函数再看这道题的话，流程是一样的，创建，问题拆分，返回。

一般难点在于问题拆分部分，想要节省空间可以从创建部分下手，部分情况下可以降低数组维度。

以上。

（其实比较难的题，我自己拆分问题很多情况下也拆不好hhhhh，看看题解吧。）