最近准备工作面试，学习动态规划算法，虽然思想倒是很好理解，但当遇到问题时，自己却无从下手，直至一天，天空划过一道闪电，文思泉涌，终于理解到动态规划的思想精髓，遂记录下来，以一个新手学习的过程理解动态规划。重点在以容易理解的角度出发。
什么是动态规划？
百科定义：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
通俗的定义：动态性体现在问题在动态方程作用下，从一个状态向另一个状态过渡，动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。
什么时候用动态规划？
动态规划算法适用于具有最优子结构的问题。最优子结构即是当前问题可以分解为规模较小的子问题，当前问题达到最优解，则子问题(规模较小问题)也一定达到最优解。当前问题和子问题性质相同，只是规模不同。
- l 优化暴力迭代问题
- l 解决回溯算法
- l 经典问题
0-1背包问题、青蛙跳台阶问题、换零钱问题(最小张数、最多方法数)
怎么用动态规划？
心中有个表！！
心中有个表！！
心中有个表！！
(我不是在骂人.........)
暴力迭代问题，之所以耗时是因为在迭代过程中，做许多无用的计算，之前的计算的结果没有存储，为下一次计算做调用，动态规划算法则是用空间换时间，每一次计算过程中，将计算得到的结果记录下来，为下一次的计算做调用。
关于动态规划你需要知道的事
既然是一个通用的算法，那么总要有一个数学模型，下面介绍一下动态规划的模型，理解两个核心概念。
v 状态：
描述子问题的解，或者说描述问题的解(不要忘了，子问题只是规模比问题小，其实质完全相同)。这样解释可能不好理解，举个例子：
l Dp[i][j]:表示用i元面值的货币凑够j元的最小张数。
l Dp[i-1][j]:表示用前（i-1）种面值的货币凑够j元的最小张数。
l Dp[i][j-1]:表示用i种面值的货币凑够j-1元的最小张数。
上述Dp[i-1][j]、Dp[i][j-1],Dp[i][j]即是描述这个问题的状态。
此处比如定义货币币值有[1,2,5,7,10],目标钱数target=20,则最终问题即是求dp[5][20]的值是什么？下文将详细描述这个问题的求解过程，此处理解一下什么事状态即可。
v 状态转移方程：
描述问题从一个状态转移到一个状态的表达式，即是一种递推公式，类似于数学里面的数列：给你a1,a2,a3,a4..让你求an=?.
对于上面的例子，则是告诉你Dp[i-1][j-1]、Dp[i-1][j]、Dp[i][j-1]等一系列状态，让你求Dp[i][j]是多少？
对于一个问题，用数学语言表示状态倒是不难(泄密：就是二维数组的一个格子，即是Dp[i][j]),关键点也是难点就是寻找状态转移矩阵，继而用数学表达式表示出来。如果这一步实现了，其问题求解过程就是简单填表的过程。
干巴巴数学公式看起来抽象，话不多说，举例说明动态规划的分析过程。
问题一：用最小的纸币数换取目标的钱数
问题描述：小明(就是我们心目中的小明)去商店买酱油，一瓶酱油2元，小明身上只有10元整钱，商店老板娘小红(对，也是活在我们课本里的小红)手里只有1,2,5元的币值的纸币，老板娘小红有严重的强迫症，每次都希望用最小的纸币数找给顾客，问小红最小需要用多少的纸币数？
分析过程：
(1)这个问题很显然是问：小红可以用[1,2,5]元的纸币，最小需要多少张可以凑够10-2=8元？
(2)问题是求最小纸币数得到目标的钱数
记住之前强调的：心中要有张表！！！心中要有张表！！！中要有张表！！！
问题状态=表中元素==>dp[i][j]:表示用i种面值的纸币凑够j元需要的最小的张数
(3)动态规划算法适用于具有最优子结构的问题。
如果不懂最优子结构的问题是什么问题，请转到文章前面去看。
现在把问题规模变下：
l 从纸币面值的角度缩小规模：
Dp[i-1][j]:用i-1种面值的纸币凑够j元最小需要多少张？
l 从零钱数的角度缩小规模
Dp[i][j-1]:用i种面值的纸币凑够j-1元最小需要多少张？
(4)问题状态转移方程的推导。
问题是求3种面值的纸币凑够8元，那么我们从上面两个角度出发推导状态转移方程。
试想，我们不知道凑够8元需要多少纸币，但我们如果知道凑够7元最小需要多少张，即知道Dp[3][7],那么凑够8元，只需要在Dp[3][7]+1张1元就是凑够8元的张数，当然，也可以是Dp[3][6]+1张2元，Dp[3][6]+2张1元，Dp[3][3]+1张5元，Dp[3][3]+5张1元....等等。
但是这还不一定是最少的，从纸币面值的角度出发缩小问题规模，即假如我们使用2种纸币[1,2]也可以凑够8元，最小张数为Dp[2][8],继续，我们用1种纸币面值也可以凑够8元，最小张数为Dp[1][8]。
那么最终结果是什么呢？
就是上面所有情况中，张数最小的那种情况。对于上面问题最优结果是1张5元、1张2元、1张1元。
现在对于这个问题进行抽象：
为了方便理解，此处仍然用具有的面值代替抽象的，只是除去1元的硬币。
现在假定有面值values=[2,3,5],目标钱数target=9元：
Dp[i][j]={min(dp[i-1][j],dp[i][9-count*values[i] ]),i=3,2;j-count*i>=0}
dp[i-1][j]:这部分理解为分别用1、2、3中面值的纸币凑够8元；
dp[i][9-count*i]：这部分理解为分别用i种货币，且优先选择面值最大的values[i]硬币，且张数count从1、2、3...满足条件是j-count*i>=0；
有了上面的递推公式，下面就是根据递推公式填表的过程：
(5)定义一张表，m*(n+1)的二维数组Dp[m][n+1],其中，m是硬币币值的种数，n为target钱数，如下表：行代表币值，列代表0~target钱数：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
2 |
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
下面模拟程序运行步骤进行填表：
1)首先填充第一列：即用2元凑够0元、用2、3元凑够0元、用2、3、5凑够0元；
显示所有的情况都是0张，即经过这一轮填表为
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
2 |
0 |
|
|
|
|
|
|
|
|
|
3 |
0 |
|
|
|
|
|
|
|
|
|
5 |
0 |
|
|
|
|
|
|
|
|
|
2)填充第一行：即是用2元凑够0、1、2、3...9元所需最小张数.
不难理解满足下列公式：
jj%values[0]==0 Dp[0][jj]=jj/values[0]
jj%values[0]!=0 Dp[0][jj]=65536(因为是求最小值，所以不满足情况下，设为最大值)
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
2 |
0 |
65536 |
1 |
65536 |
2 |
65536 |
3 |
65536 |
4 |
65536 |
3 |
0 |
|
|
|
|
|
|
|
|
|
5 |
0 |
|
|
|
|
|
|
|
|
|
3)下面按行填充空白的单元
Dp[1][1]:用2、3元凑够1元，显然为0(填充为65536)
Dp[1][2]:用2、3元凑够2元，显然为1
Dp[1][3]:用2、3元凑够3元，显然为1
Dp[1][4]:用2、3元凑够4元，显然为2
依次类推....
Dp[2][9]=min{Dp[1][9],Dp[2][9-1*5],Dp[2][9-2*5]},显然删除线部分不满足target-count*values[i]>=0的条件。
4)最终填充的表格如下：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
2 |
0 |
65536 |
1 |
65536 |
2 |
65536 |
3 |
65536 |
4 |
65536 |
3 |
0 |
65535 |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
5 |
0 |
65535 |
1 |
1 |
2 |
1 |
2 |
2 |
2 |
3 |
5)我们问题求解的结果是Dp[3][9]=3
6)至此问题解决。
所以归纳下来，动态规划求解过程有以下几步：
1)定义状态，即如何定义一张表
2)归纳推导递推方程
3)填充表的第一列
4)填充表的第一行
5)填充表的余下单元
6)求出最终结果。
此题具体代码详见文章http://blog.csdn.net/u013291818/article/details/57082263
问题二：一定面值的纸币，换取目标钱数，最多有多少种换法？
仍然以问题一种数据举例：
硬币面值 values[3]=[2,3,5],target = 9;
(1)定义状态。
Dp[i][j]:用i种面值的硬币，凑够j元最多方法数
(2)归纳推导递推方程。
Dp[i][j]={Dp[i-1][j]+Dp[i][j-1*values[i]]+Dp[i][j-2*values[i]]+Dp[i][j-count*values[i]]} j-count*values[i]>0
上述公式很好理解：
我们固定一个币值的硬币：
Dp[i-1][j]：用0张values[i]面值的硬币的方法数
Dp[i][j-1*values[i]]：用1张values[i]面值的硬币的方法数
Dp[i][j-2*values[i]]：用2张values[i]面值的硬币的方法数
.......
Dp[i][j-count*values[i]]：用count张values[i]面值的硬币的方法数,其中j-count*values[i]>0
则最终Dp[i][j]即是上述方法的和。
(3)填表
具体填表方法与问题一相同，只是条件改变
jj%values[0]==0 Dp[0][jj]=jj/values[0]
jj%values[0]!=0 Dp[0][jj]=0(因为是求最大值，所以不满足情况下，设为最小值)
(4)求出最终结果。
此题具体代码见
http://blog.csdn.net/u013291818/article/details/56851079
问题三：青蛙跳台阶
问题描述：一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
可以将问题转换硬币问题：
青蛙只有两种选择：跳一级台阶和跳2级台阶，即是面值只有[1,2]两种面值
青蛙跳上N级台阶有多少种跳法？：即是目标钱数为N，有多少种方法。
现在这个问题转换为问题二。此处不再赘述。
对于上述三个问题的描述，应该能够理解动态规划的解题方法，博主处于学习阶段，理解也许有偏颇之处，文中如有描述错误之处，还请指出，共同进步。【不要吝啬你的赞】