众所周知，一个算法可以使用动态规划，务必需要满足两个条件，一 最优子结构；二 折叠子问题。本文通过对若干问题使用动态规划算法下的最优子结构和折叠子问题性质进行综合分析，由简单到复杂，总结出使用动态规划解决问题的一般解题思路。

问题一：【青蛙跳格】一只青蛙一次能跳一格或者两格，求青蛙跳到n格有多少种跳法。 最优子结构性质： 该问题可以转换为求青蛙跳到n格的最多跳法，假设青蛙跳到n-2格有x种跳法，跳到n-1格有y种跳法，则青蛙跳到n格的最多跳法必然包含了max（x）+max（y）,假设x不是最大值，则在n-2格必然存在z>x，使得该问题的解为z+y，显然与原来的解矛盾，因此该问题符合最优子结构性质。 折叠子问题： 该问题的折叠子问题其实已经在上述最优子结构的阐述种表明，想要求初n格的值，必须求出n-2和n-1格的值。 综上，该问题可以用动态规划来解决。

问题二：【理发师问题】给定一个数组，包含n个数，从中选出一些数，规定不能选相邻的数，设计一种选择方案，使得选出的数和最大，输出最大值。例：3 2 7 4 1 ；最大和：11 最优子结构性质： 该问题属于【01背包问题】的一种，即给定一个序列，在固定【限界函数】下，选出符合要求的最优解或者可行解。01背包问题的限界函数是剩余重量，该问题则是不相邻数组。该题中，当选择第i个元素后，则数组a[0：i-2]以及a[i+1：n]数组中（不相邻元素组成的数组）所进行的选择一定为最大和，反例可以简单证明，不再赘述。 折叠子问题： 由于每次的选择都需要考虑前面已经选择的不相邻数组最优值情况，因此一段数组的最优解务必会被多次使用，符合折叠子问题性质。 综上，该问题可以用动态规划来解决。

问题三：【可被三整除的最大数】给定一个数组，设计算法从中选择若干个数，使得这些数字的和可以被三整除，输出符合条件的最大数和。例：数组：3 6 5 1 8 ； 最大和：18 最优子结构性质： 该问题同样属于【01背包问题】，对于第i个数，有三种情况，模3余0、1、2，若余0，而如果两个数的余数和为3，则两个数相加，可以被3整除，因此对于这三种情况，分别对应前数组i-1解的余0、2、1，同样，此前的解一定是其数组范围内的最优解。 折叠子问题： 由递推性质可知，当前解的计算包含了此前所计算的所有最优解，即一个解将被多次调用，符合折叠子问题性质。

问题四：【石子合并问题】给定一堆石子，规定一次只能选择相邻石子合并，合并后得到合并分数为合并石子的总数，设计一种合并算法，使得合并总分最大。例：石子：4 4 5 9；最大得分：54 最优子结构性质： 该问题属于【矩阵连乘问题】，需要考虑从何处划分合并。若直接考虑最后一次合并，所合并的两堆石子一定是对应两堆石子数量下的最大合并分数，即结果最优，子问题最优，符合最优子结构性质。 折叠子问题： 当合并只剩下两堆石子时，最大值增量=两堆石子的最大合并值。第一堆最大值的增量=倒数第二次次合并的最大值……每次计算一次合并时，都需要重复调用此前已经计算的子问题的解，符合折叠子问题性质。

20201219更新： DP算法为什么会比穷举法要快很多？ DP在设计最优子结构性质时，舍弃了一部分不可能构成结果的解，换句话说，DP自带剪枝。

当思考状态转移方程时，对于限界函数的限制范围，需要思考，随着状态转移，限制是不是也在更新。