动态规划的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题(阶段)。按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部最优解。依次解决各子问题，最后一个子问题就是初始问题的解。

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推的方式去解决。则动态规划的本质是状态的定义和状态转移方程

动态规划通过拆分问题，将原始问题拆分为子问题，而各子问题之间的关系是后一子问题的解往往由前一子问题的解求出，则**子问题之间是重叠的(则不是相互独立的)**，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

动态规划与分治法最大的差别是:适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

动态规划与贪心法的区别

动态规划其实是贪心法的一般情况，而贪心法是动态规划的特殊情况，为什么这么说呢，下面就来解释下，

用动态规划来求解时总是将问题拆分，找到递推公式，则将各个状态定义为dp[i],结果为result，动态规划求解的流程图如下：

但是在大多数动态规划求解的过程中后一子问题一般是从前面多个子问题中得出的(也可能是前面所有的子问题)，则流程图如下：

而贪心算法往往只是有前一子问题而得出后一子问题的，则从上面的两个图中可以得出动态规划与贪心算法的关系，如果后一子问题只是由前一子问题推出，则为贪心，如果后一子问题由前面多个子问题推出，则为动态规划，所以说贪心是动态规划的特殊情况。

动态规划常见问题

最长子串

给定一个字符串，找到没有重复字符的最长子串的长度。

例如:
字符串”abcabcbb”, 最长非重复子串长度是3(“abc”).
字符串”pwwkew”, 最长非重复子串长度是3(“wke”).

具体解法移步[数据结构算法之leetcode Longest Substring](http://bigdatadecode.top/数据结构算法之leetcode Longest Substring.html)

最长回文

给定一个字符串，求最长回文子串(假设字符串中只有唯一的一个最长回文子串)。

例如：
字符串”bananas”, 最长回文为”anana”
字符串”aaa”, 最长回文为”aaa”

具体解法移步[数据结构算法之leetcode Longest Palindromic](http://bigdatadecode.top/数据结构算法之leetcode Longest Palindromic.html)