动态规划是一种思想
动态规划算法，这种叫法我想你应该经常听说。嗯，从道理上讲这么说我觉得也没错，首先动态规划它不是数据结构，这一点毋庸置疑，并且严格意义上来说它就是一种算法。
但更加准确或者更加贴切的提法应该是说动态规划是一种思想。
那什么是思想？算法和思想又有什么区别呢？
一般来说，我们都会把算法和数据结构放一起来讲，这是因为它们之间密切相关，而算法也往往是在特定数据结构的基础之上对解题方案的一种严谨的总结。
比如说，在一个乱序数组的基础上进行排序，这里的数据结构指的是什么呢？很显然是数组，而算法则是所谓的排序。至于排序算法，你可以考虑使用简单的冒泡排序或效率更高的快速排序方法等等来解决问题。
没错，你应该也感觉到了，算法是一种简单的经验总结和套路。那什么是思想呢？相较于算法，思想更多的是指导你我来解决问题。
比如说，在解决一个复杂问题的时候，我们可以先将问题简化，先解决简单的问题，再解决难的问题，那么这就是一种指导解决问题的思想。另外，我们常说的分治也一种简单的思想，当然它在诸如归并排序或递归算法当中会常常被提及。
而动态规划就是这样一个指导我们解决问题的思想：你需要利用已经计算好的结果来推导你的计算，即大规模问题的结果是由小规模问题的结果运算得来的。这句话对于你充分理解动态规划的基本原理十分重要，希望你能记下来。简单理解的话，你可以这样认为：算法是一种经验总结，而思想则是用来指导我们解决问题的。
动态规划问题的典型特点
事实上，动态规划是运筹学上的一种最优化方法，只不过在算法问题上应用广泛。接下来我们就深挖一层，看看动归问题所具备的一些特点。
求“最”优解问题（最大值和最小值）除非你碰到的问题是简单到找出一个数组中最大的值这样，对这种问题来说，你可以对数组进行排序，然后取数组头或尾部的元素，如果觉得麻烦，你也可以直接遍历得到最值。
不然的话，你就得考虑使用动态规划来解决这个问题了。
既然说了动态规划用来解决最优问题，并且是全局最优问题。那就要求我们的算法具有所谓的”大局观“，那我们就需要知到我们之前的状态，这样才能保证我们当前的状态最优。也就是通过了记忆化递归 或者 递推。本质都是将我们的计算结果保存下来，也称之为状态。对于上面的题目就可以理解为一个最简单的动态规划，对于数据的从第0个到第i个值都有一个最大值max i，对于max i + 1 = max（i+ 1，max i + 1）也是就是上述问题的递推公式了。这里面反映的只是一种思想，我们的一切储存都是为了标志我们之前的状态来保证现在的最优。
网友评论