已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”）
此时，如果把问题规模降到0，即已知A0，可以得到A0->B.
然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：
上述两种状态转移图如下图所示：
能用动规解决的问题的特点
能采用动态规划求解的问题的一般要具有3个性质：
(1)最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2)无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
动规解题的一般思路
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
图1动态规划决策过程示意图
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解
算法实现的说明
动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。
使用动态规划求解问题，最重要的就是确定动态规划三要素：
（1）问题的阶段（2）每个阶段的状态
（3）从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。
f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+P(n,m)}
算法实现的步骤
1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。
注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述
2、设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。
3、找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。
4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。
代码基本框架：
下面通过几个典型例子，从简单到难帮助我们理解动态规划。
1、斐波那契数列
斐波那契数列大家都很熟悉，而且知道用递归可以很容易的做出来
如果用动态规划，就是把结果存到一个数组中。
与之类似的还有：跳台阶问题：每次只能跳一个或者两个台阶，跳到n层台阶上有几种方法
填充长方体问题：将一个2*1的长方体填充到2*n的长方体中，有多少种方法
2、数组最大不连续递增子序列
arr[]={3,1,4,1,5,9,2,6,5}的最长递增子序列长度为4。即为：1,4,5,9
设置一个数组temp，长度为原数组长度，数组第i个位置上的数字代表0...i上最长递增子序列，当增加一个数字时，最大递增子序列可能变成前面最大的递增子序列+1，也可能就是前面最大递增子序列，这需要让新增加进来的数字arr[i]跟前面所有数字比较大小，即当arr[i]>arr[j]，temp[i]=max{temp[j]}+1，其中，j的取值范围为：0,1...i-1，当arr[i] 3、数组最大连续子序列和 如arr[]={6,-1,3,-4,-6,9,2,-2,5}的最大连续子序列和为14。即为：9,2,-2,5 创建一个数组a，长度为原数组长度，不同位置数字a[i]代表0...i上最大连续子序列和，a[0]=arr[0]设置一个最大值max，初始值为数组中的第一个数字。当进来一个新的数字arr[i+1]时，判断到他前面数字子序列和a[i]+arr[i+1]跟arr[i+1]哪个大，前者大就保留前者，后者大就说明前面连续数字加起来都不如后者一个新进来的数字大，前面数字就可以舍弃，从arr[i+1]开始，每次比较完都跟max比较一下，最后的max就是最大值。 4、数字塔从上到下所有路径中和最大的路径 数字塔是第i行有i个数字组成，从上往下每个数字只能走到他正下方数字或者正右方数字，求数字塔从上到下所有路径中和最大的路径，如有下数字塔 3 15 843 2679 62351 最大路径是3-5-3-9-5，和为25。我们可以分别从从上往下看跟从下往上看两种动态规划的方式去解这个题 从上往下看：当从上往下看时，每进来新的一行，新的一行每个元素只能选择他正上方或者左左方的元素，也就是说，第一个元素只能连他上方的元素，最后一个元素只能连他左上方的元素，其他元素可以有两种选择，所以需要选择加起来更大的那一个数字，并把这个位置上的数字改成相应的路径值，具体过程如下图所示 3333 15484848 843843121211121211 26792679267914181920 6235162351623512020222521 所以最大值就是最底层的最大值也就是25。 具体运算过程就是，建立一个n*n的二维数组dp[][]，n是数字塔最后一行的数字个数，二维数组每一行数字跟数字塔每一行数字个数一样，保存的值是从上方到这一个位置最大路径的值，填入边界值dp[0][0]=3，每一行除了第一个值跟最后一个值，其他的值选择上方或者左上方更大的值与这个位置上的值相加得来的值，即dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+n[i][j] 优化：动态规划中每一个需要创建一个二维数组的解法，都可以换成只创建一个一维数组的滚动数组解法，依据的规则是一般二维数组中存放的是所有的结果，但是一般我们需要的结果实在二维数组的最后一行的某个值，前面几行的值都是为了得到最后一行的值而需要的，所以可以开始就创建跟二维数组最后一行一样大的一维数组，每次存放某一行的值，下一次根据这一行的值算出下一行的值，在存入这个数组，也就是把这个数组滚动了，最后数组存储的结果就是原二维数组中最后一行的值。 拿到本题来说，开始创建一个一维数组dp[n]，初始值只有dp[0]=3，新进来一行时，仍然遵循dp[i][j]=Math.max(dp[i-1][j-1],dp[i-1][j])+n[i][j]，现在为求dp[j]，所以现在dp[i-1][j]其实就是数组中这个位置本来的元素即dp[j]，而dp[i-1][j-1]其实就是数组中上一个元素dp[j-1]，也就是说dp[j]=Math.max(dp[j],dp[j-1])+n[i][j] 这样空间复杂度就大幅度下降了。 从下往上看时：从下往上看时大体思路跟从上往下看一样，但是要简单一些，因为不用考虑边界数据，从下往上看时，每进来上面一行，上面一行每个数字有两条路径到达下面一行，所以选一条最大的就可以 33325 1515151822 843843171617171617 2679891214891214891214 62351623516235162351 具体方法也是建立一个二维数组，最下面一行数据添到二维数组最后一行，从下往上填数字，所以状态转化方程是dp[i][j]=Math.max(dp[i+1][j+1],dp[i+1][j])+n[i][j]，具体解决方法跟从上往下看一样，就不写具体代码了。 优化：滚动数组，只创建一个一维数组，数组初始值是数字塔最下面一行的值，每次新加一行值，将数组中的值改变，最后数组中第一个数字就是最大路径的值。状态转化方程就是temp[j]=Math.max(temp[j],temp[j+1])+n[i][j]。具体代码如下 从下往上看跟从上往下看相比，虽然逻辑较为简单，但是从下往上看时需要得到完整的数字塔之后才能开始计算，而从上往下看时可以随着数字塔的深入来计算，也可以返回任意一层的结果，是最好的方法。 5、两个字符串最大公共子序列 比如字符串1：BDCABA；字符串2：ABCBDAB，则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA 具体思想：设X=(x1,x2,.....xn)和Y={y1,y2,.....ym}是两个序列，将X和Y的最长公共子序列记为LCS(X,Y)，如果xn=ym，即X的最后一个元素与Y的最后一个元素相同，这说明该元素一定位于公共子序列中。因此，现在只需要找：LCS(Xn-1，Ym-1)就好，LCS(X,Y)=LCS(Xn-1，Ym-1)+1；如果xn!=ym，这下要麻烦一点，因为它产生了两个子问题：LCS(Xn-1，Ym)和LCS(Xn，Ym-1)。 动态规划解法：先创建一个解空间即数组，因为给定的是两个字符串即两个一维数组存储的数据，所以要创建一个二维数组，设字符串X有n个值，字符串Y有m个值，需要创建一个m+1*n+1的二维数组，二维数组每个位置（i，j）代表当长度为i的X子串与长度为j的Y的子串他们的最长公共子串，之所以要多创建一个是为了将边界值填入进去，边界值就是第一行跟第一列，指X长度为0或者Y长度为0时，自然需要填0，其他位置填数字时，当这两个位置数字相同，dp[i][j]=dp[i-1][j-1]+1；当这两个位置数字不相同时，dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j])。最后二维数组最右下角的值就是最大子串。 6、背包问题 在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数），求背包能够容纳的最大价值。 像这种固定数值的组合问题，比如这个问题的W总容量，跟下个实例零钱问题的总钱数，都是适合用动态规划来解决的问题，对于这样的问题，动态规划的解法就是：创建一个二维数组，横坐标是从1开始到W，纵坐标是组成W的各种元素，本题中就是指W1，W2……Wn，数组中每个位置（i，j）的数字就是当组成元素只有W1，W2……Wi，背包可放容量为j时的结果，本题中就是容纳的最大价值。所以很容易分析出，当（i，j）时，如果Wi能放的下，空间减小，但是会增加Pi的价值，如果Wi不能放的下，空间不变，是（i-1，j）的价值，取其中最大值就好了，即状态转化方程为能放的下，dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+p[i])；放不下，dp[i][j]=dp[i-1][j]； 优化：滚动数组，只创建一个一维数组，长度为从1到W，初始值都是0，能装得下i时，dp[j]=Math.max(dp[j],dp[j-w[i]]+p[i])；装不下时，dp[j]=dp[j]; 7、找零钱问题：有几种方法 具体思路同背包问题，这里只分析一下动态转化方程，能用这种零钱，分为用了这种零钱的方法跟没用到这种零钱的方法，dp[i][j]=dp[i-1][j]+dp[i][j-num[i]]；如果不能用这种零钱，即所组成的面额小于当前零钱，直接等于不用这种零钱的数值，dp[i][j]=dp[i-1][j]。这里要特别注意的是。1、开始填写二维数组边界值时，第一行是填写只用第一种面额零钱组成相应数额的方法，要注意是总数额除以第一种面额取余为0才能组成，即如果第一种面额为2，不能组成3,5的数额等；2、填写二维数组第一列时，代表到用到面额为i时，剩余数额为0，即只用i就可以组成相应数额，这也是一种方法，所以第一列的值，第一个为0，后面全为1. 优化：动态数组，同背包问题即以上分析。 8、找零钱问题：所用面额数量最少 优化：滚动数组，具体思路一样 动态规划和分治区别： 总结： 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。