动态规划最为一个比较常见的算法类型，在做算法题的时候经常会遇到，下面我根据我个人见解结合网上知识总结一下动态规划的使用情景与一些问题解答。
背景
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。
使用情境
要使用动态规划需要满足最优化原理和无后效性，并以牺牲空间复杂度的前提优化时间复杂度，选用的时候需要考量是否有更优的算法。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解会重复计算很多相同的子问题，利用动态规划的思想可以减少计算量。
最优化原理
一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
无后效性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
例子一、最长回文子串
题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设s 的最大长度为 1000。
解题思路：首先要思考：怎样的字串满足回文子串。若是单一一个字符，它是满足回文子串定义的；当大于等于两个字符形成回文子串则要求从中间往两侧满足字符逐个相等。所以一个字串要想是回文字串，则要除去两侧，原来内部满足回文字串的同时，还要满足左右两个字符相等，即P(i,j)=P(i+1,j−1)∧(Si==Sj)。然后只要比较当前操作子串与最长回文子串并选取较长者即可。
代码及步骤：
图解：
例子二、最长子序和
题目：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
解题思路：该题要求求取最长的子序和，可以用这样的角度进行思考：在遍历到某个元素时进行判断，判断前面最优子序加上这个元素的和更大还是单这个元素更大些，该元素更大则舍弃原来子序，若加上前面的子序更大，则子序加上该元素作为下一个遍历元素的前子序再进行判断。结束后取最大子序和即可。
代码及步骤：
图解
例子三、零钱兑换
题目：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。
解题思路：取最后一枚硬币之前的最优解加一的最小值即为当前最优解，如coins=[1,3,5]，amount=6，则判断amount=6-1或6-3或6-5的最优解加一即为amount=6的最优解。
代码及步骤：
图解：
总结
可以看出，动态规划基本上都是在确定的历史上进行延续操作，这些历史会被取出来存放在额外空间数组内。动态规划的核心还是求取最优的理念，当遇到求最大，最长，最少之类的问题时就可以考虑一下使用动态规划，简单模拟一下情景，画个图，思路理清后代码编写就不困难了。
