本文总结了几种常见动态规划算法的分析策略，但不做案例的具体分析，阅读前最好对这几种算法有一定基础了解。
 


 
动态规划策略


 


1.动态规划介绍

 
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。
 
基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
 
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。
 
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。
 


 
2.动态规划求解步骤
 
（1）  确定最优解结构
 
（2）  递归定义最优解的值
 
（3）  自底向上计算最优解的值
 
（4）  重构最优解
 


 


 
几种动态规划算法策略分析
 

  

 
 
1.装配线调度问题
 

 
分析：首先确定最优解结构，分析问题可知大致分为两种情况： 
 
从第一个站出站（j=1）和从第j个站出站（j>=2）。
 


 


 


 
当j=1：货物上线后只经过一个站，f1[j]=e1+a1,1
 
当j>=2，又可分为跳线和不跳线两种情况：
 
不跳线：f1[j]=f1[j-1]+a1,j
 
跳线：当货物从f2跳到f1，有一个跳转时间t2,j-1，则：f1[j]=f2[j-1]+t2,j-1+a1,j
 
由对称关系，f2[j]可同理得出，最后：
 

 

 
传输完后，加上自动下线时间x1,x2,总装配时间：
 


 

 
最后采用自底向上的方法求解算法并递归的输出最优解的值。
 


 
2.矩阵链乘问题
 

 
分析：若只有一个矩阵，无最优解。若大于一个矩阵：对于A1,A2,…,An，我们得在和之间加上一个括号使得分开的两个子矩阵链乘积最小，再分别对两个子问题找到最优的划分结果：
 
设m[i,j] 为计算矩阵链Ai..j 的乘积所需的最少标量乘法次数。
 
若：i=j，不需任何计算，即m[i,j]=0，否则：
 


 

 
则最终公式为：
 


 


 
在计算时，采用了自底向上的方法来求解最优解，在求解过程中用一个辅助的数组S[1….n-1,2….n]来记录最优值m[i，j]对应的分割点K，这样能够构造出最优解。最后，借助辅助数组递归的输出最优解的值。
 


 
3.最长公共子序列(LCS)
 

 
分析：可分为最后一个元素相同和不相同两种情况：
 
最后一个元素相同：求X[1…m-1]和Y[1…n-1]两个子序列的最长公共子序列。
 
最后一个元素不同：求X[1…m-1]和Y[1…n]或者X[1…m-1]和Y[1…n]两个子序列的最长公共子序列。
 
令C[i,j]为的LCS的长度，如果i=0或者j=0则LCS=0，则根据LCS的最优子结构特征我们可以构造出：
 





 
根据递归式，我们能写出一个递归算法来计算最长公共子序列，由于LCS的子问题过多，所以我们采用自底向上的计算。
 
在这个过程中，我们需要借组一个数组b[i,j]来记录最优解得构造过程，利用b[i,j]所记录的元素来输出最优解。


4.最大子段和

分析:求给定的n个整数（可能但不全为负）a1,a2,…,an, 的i跟j，使 ai 到 aj 的和最大。我们定义b[j]=max(sum(i:j))，
为从i到j子段的最大子段和。我们比较b[j-1]+a[j]和a[j]的大小,如果b[j-1]<0,显然b[j-1]不是最大子段，此时b[j]=a[j]。反之，我们令b[j-1] + a[j] = b[j],找出最大的子段和。
则：b[j]=max( b[j-1]+a[j], a[j] ), 1<=j<=n
由上面的递归公式我们可以写出一个自底向上的递归算法，在算法中我们借助一个变量sum来记录过程中的最大子段和，若此时的b[j]>sum，更新sum中的值，反之，继续求解。直到程序进行完毕，输入sum中的最大子段和。


5.0-1背包问题
分析：分数背包问题可以采用贪心策略解决，但我们在求解0-1背包问题时，我们只能采用动态规划策略。
同样地：首先构造最优子结构。令c[i,j]表示利用前i个物品装容量为j的背包所能获得的最大价值，可分两种情况：
含物品n：去掉第n个物品，用W-wn容量的背包装物品1,2，…,n-1：c[i,j]=c[i-1,j-wi]+vi
不含物品n：用W容量背包装物品1,2,…,n-1：c[i,j]=c[i-1,j]
当然，没有物品或没有容量，c[i,j]=0
则总的递归式：



有上述递归方程，就可写出相应递归算法，但该递归算法复杂度太高，可用V[0..n,0..W]来保存子问题(i,j)的最大值。b[1..n,1..W]用来保存所做出的最优选择，以便构造最优解。在计算最优解的时候，保存所做出的最优决策，便可得到最优解。




两种解决策略

 


1.自底向上策略
一般动态规划问题都是基于此策略。在用这种方法时一般需要恰当的定义子问题的规模，使得任何子问题都只依赖于更小的子问题的求解。我们可以将问题的规模按照由大到小排列依次求解。每个子问题都只求解一次。


2.自顶向上(备忘录)策略

动态规划有一个性质为子问题重叠性质，就是对于子问题在递归过程中不断求解，虽然问题规模很小，但是求解次数会非常多，造成程序运行非常慢。在使用自顶向下的求解过程中，我们一般要设计一个备忘录，在递归求解过程中对于已经求解过的问题保存在备忘录中，当下次要使用时直接拿出来，不用再次求解。


3.优缺点分析

自顶向下只需要求解问题需要的解，不需要对所有子问题都去求解。但是它需要额外的递归开销。自底向上必须对所有子问题进行求解但是可有效减少计算时间和所需的存储空间。


总结

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。解决动态规划问题的关键是找到最最优子结构并定义出递归式，根据经验，通常会分为若干种情况分开讨论，尤其注意容易遗漏的特殊情况（0、1、相等…）。在求解计算时，如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
 

数据挖掘常见分析方法
 
一、回归分析
 
目的：
 
设法找出变量间的依存(数量)关系, 用函数关系式表达出来。
 
所谓回归分析法，是在掌握大量观察数据的基础上，利用数理统计方法建立因变量与自变量之间的回归关系函数表达式（称回归方程式）。
 
回归分析中，当研究的因果关系只涉及因变量和一个自变量时，叫做一元回归分析；当研究的因果关系涉及因变量和两个或两个以上自变量时，叫做多元回归分析。
 
此外，回归分析中，又依据描述自变量与因变量之间因果关系的函数表达式是线性的还是非线性的，分为线性回归分析和非线性回归分析。通常线性回归分析法是最基本的分析方法，遇到非线性回归问题可以借助数学手段化为线性回归问题处理。
 
回归分析法是定量预测方法之一。它依据事物内部因素变化的因果关系来预测事物未来的发展趋势。由于它依据的是事物内部的发展规律，因此这种方法比较精确。测报工作中常用的是一元线性回归和多元线性回归模型。
 
一元线性回归是指事物发展的自变量与因变量之间是单因素间的简单线性关系，它的模型可以表示为: y=a+bx
 
其中y是因变量，x是自变量，a是常数，b是回归系数。
 
多元线性回归是指一个因变量与多个自变量之间的线性关系。模型的一般型式为：
 
y=a+b1x1+b2x2+…+bnxn
 
其中，y是因变量，x1、x2、…xn是自变量，a是常数，b1、b2、…bn是回归系数。
 
logistic回归（logistic regression）是研究因变量为二分类或多分类观察结果与影响因素（自变量）之间关系的一种多变量分析方法，属概率型非线性回归。
 
logistic回归的分类：
 
（1）二分类资料logistic回归：因变量为两分类变量的资料，可用非条件logistic回归和条件logistic回归进行分析。非条件logistic回归多用于非配比-对照研究或队列研究资料，条件logistic回归多用于配对或配比资料。
 
（2）多分类资料logistic回归：因变量为多项分类的资料，可用多项分类logistic回归模型或有序分类logistic回归模型进行分析。 
 
 
 
二、分类分析
 
（1）决策树
 
决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant。 决策树是应用最广的归纳推理算法之一，一种逼近离散值目标函数的方法，对噪声数据有很好的健壮性且能学习析取表达式。
 
决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。
 
决策树使用的问题：
 
1）实例是由属性-值对表示的；2）目标函数具有离散的输出值；3）可能需要析取的描述；4）训练数据可以包含错误；5）训练数据可以包含缺少属性值的实例。
 
决策树属性的选择：构造好的决策树的关键在于如何选择好的逻辑判断或属性。对于同样一组例子，可以有很多决策树能符合这组例子。人们研究出，一般情况下或具有较大概率地说，树越小则树的预测能力越强。要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性。 
 
决策树的优点：可以生成可以理解的规则；计算量相对来说不是很大；可以处理连续和离散字段；决策树可以清晰的显示哪些字段比较重要。
 
决策树的缺点：对连续性的字段比较难预测；当类别太多时，错误可能会增加的比较快；一般的算法分类的时候，只是根据一个属性来分类。；不是全局最优。
 
（2）人工神经网络
 
人工神经网络是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。人工神经网络是由人工建立的以有向图为拓扑结构的动态系统，它通过对连续或断续的输入作状态相应而进行信息处理。
 
人工神经网络的特点:可以充分逼近任意复杂的非线性关系；所有定量或定性的信息都等势分布贮存于网络内的各神经元，故有很强的鲁棒性和容错性；采用并行分布处理方法，使得快速进行大量运算成为可能；可学习和自适应不知道或不确定的系统；能够同时处理定量、定性知识。 
 
 
 
三、相关性分析
 
研究现象A，B之间是的某种依存关系，或者研究变量X，Y之间的相互依存关系的密切程度。就是对总体中确实具有联系的标志进行分析，其主体是对总体中具有因果关系标志的分析。它是描述客观事物相互间关系的密切程度并用适当的统计指标表示出来的过程。例如：在一段时期内出生率随经济水平上升而上升，这说明两指标间是正相关关系；而在另一时期，随着经济水平进一步发展，出现出生率下降的现象，两指标间就是负相关关系。
 
 
 
四、聚类分析
 
聚类是一个将数据集划分为若干组或类的过程，并使得同一个组内的数据对象具有较高的相似度而不同组中的数据对象是不相似的。相似或者不相似描述的是基于数据描述属性的取值来确定的。通常是利用各对象间的距离来进行表示。
 
数据挖掘领域的聚类算法有很多种，其中k-means聚类算法是最简单而且非常有效的聚类算法。采用k-means聚类算法对整个用户空间进行聚类的主要步骤如下:
 
（1）随机选择k个用户作为种子节点，将k个用户对项的评分数据作为初始的聚类中心。
 
（2）对剩余的用户集合，计算每个用户与k个聚类中心的相似性，将每个用户分配到相似性最高的聚类中。
 
（3）对新生成的聚类，计算聚类中所有用户对项的平均评分，生成新的聚类中心。
 
（4）重复以上2到3步，直到聚类不再发生改变为止。
 
例如：通过分组聚类出具有相似行为的客户，并分析客户的共同特征，可以更好的帮助电子商务的用户了解自己的客户，向客户提供更合适的服务。
 
 
 
五、判别分析
 
判别分析是按照一定的判别准则，建立一个或多个判别函数，用研究对象的大量资料确定判别函数中的待定系数，并计算判别指标。据此即可确定某一样本属于何类。例如：为了确诊某种疾病，需要将病人的各项检测指标同各种典型的病历做对照，从而判断其最可能属于哪种疾病。
 
 
 
六、主成分分析
 
设法将原来的变量重新组合成一组新的互相无关的几个综合变量，同时根据实际需要从中可以取出几个较少的总和变量尽可能多地反映原来变量的信息的统计方法叫做主成分分析或称主分量分析，也是数学上处理降维的一种方法。
 
 
 
七、因子分析
 
根据相关性的大小把变量分组，使得同组内的变量相关性高，不同组变量的相关性较低，然后在每一个组内提炼出一个公因子。
 
从大量的指标中提取有代表性的共性因子，比如客户忠诚度，满意度等。      主成份分析是寻找一种逼近，能够最大可能的描述数据的变化(variability)。因子分析可以理解为一个隐变量模型。由此可以说，因子分析某种程度上是一个参数模型 
 
 
 
八、时间序列分析
 
    根据系统观测得到的时间序列数据，通过曲线拟合和参数估计来建立数学模型的理论和方法。 
 
常用在国民经济宏观控制、区域综合发展规划、企业经营管理、市场潜量预测、气象预报、水文预报、地震前兆预报、农作物病虫灾害预报、环境污染控制、生态平衡、天文学和海洋学等方面。
 
 
 
常见应用以及采用的分析技术：
 
n  客户流失 (分类模型、Logistic回归算法)
 
n  用户流失预测 (分类模型、神经网络、Logistic回归算法) 购买倾向预测 (分类模型、Logistic回归算法)
 
n  增量销售预测 (分类模型、Logistic回归算法)
 
n  客户价值增长预测 (分类模型、Logistic回归算法) 
 
n  竞争对手流失预测 (分类模型、Logistic回归算法)
 
n  客户级别打分 (分类模型、Logistic回归算法) 
 
n  点击率分析(聚类模型、偏差检测、Logistic回归算法) 
 
n  网站访问行为分析（聚类模型）
 
n  客户分群 (聚类模型、K-Means算法)
 
n  购物篮分析 (关联规则)
 
n  。。。。
 
 
 
 

源码的分析，一般分析两种数据，一种是类的关系，一种是某个功能实现的流程图。下面主要说的是流程图的分析。
 
android 中源码分析的方法总得来说有两种，第一种是借助 android studio 或者 eclipse 静态代码分析的方法，查看函数或者变量的使用情况，比如查看函数的调用树，变量的数据流。第二种是借助 debug 工具或者 log 日志在代码动态执行的过程中查看程序的执行情况。
 
在 android studio 中使用 alt + f7，可以快速查看某个符号被使用的位置，包括函数名、字段名、变量名等等，还可以快速查看到该函数的调用树，变量的数据流
如果代码执行逻辑我们自己可控制，在我们可以控制的地方添加 log 打印，可以很快检测该分支逻辑执行情况；如果代码不是我们自己可以控制的，就只能使用 debug 调试查看代码分支的执行起情况了
在 debug 的时候使用跳转到函数的内部，可以追踪到 framework 层源码的执行逻辑
在 debug 的时候可以看到函数的调用栈，能够一下子就明白在这种场景下，该函数在什么时候被谁调用了
 
这就是一动一静，动静结合。

理解动态规划
 

 
 
 
动态规划中递推式的求解方法不是动态规划的本质。
 

 我曾经给学校参加NOIP的同学多次讲过动态规划，我试着讲一下我理解的动态规划，争取深入浅出。希望你看了我的答案，能够喜欢上动态规划。
 
 0. 动态规划的本质，是对问题状态的定义 和状态转移方程 的定义。
 引自维基百科
  
 
 dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
 
动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。
 本题下的其他答案，大多都是在说递推的求解方法，但如何拆分问题，才是动态规划的核心。
 而拆分问题，靠的就是状态的定义和状态转移方程的定义。
  
1. 什么是状态的定义？
 
首先想说大家千万不要被下面的数学式吓到，这里只涉及到了函数相关的知识。
 我们先来看一个动态规划的教学必备题：
  
 
 给定一个数列，长度为N，
 求这个数列的最长上升（递增）子数列（LIS）的长度.
 以 1 7 2 8 3 4 为例。
 这个数列的最长递增子数列是 1 2 3 4，长度为4；
 次长的长度为3， 包括 1 7 8; 1 2 3 等.
 
要解决这个问题，我们首先要定义这个问题和这个问题的子问题。
 有人可能会问了，题目都已经在这了，我们还需定义这个问题吗？需要，原因就是这个问题在字面上看，找不出子问题，而没有子问题，这个题目就没办法解决。
 
 所以我们来重新定义这个问题：
  
 
 给定一个数列，长度为N，
 设为：以数列中第k项结尾的最长递增子序列的长度.
 求 中的最大值.
 
显然，这个新问题与原问题等价。
 而对于来讲，都是的子问题：因为以第k项结尾的最长递增子序列（下称LIS），包含着以第中某项结尾的LIS。
 
 上述的新问题也可以叫做状态，定义中的“为数列中第k项结尾的LIS的长度”，就叫做对状态的定义。
 之所以把做“状态”而不是“问题” ，一是因为避免跟原问题中“问题”混淆，二是因为这个新问题是数学化定义的。
 
 对状态的定义只有一种吗？当然不是。
 我们甚至可以二维的，以完全不同的视角定义这个问题：
  
 
 给定一个数列，长度为N，
 设为：
 在前i项中的，长度为k的最长递增子序列中，最后一位的最小值. .
 若在前i项中，不存在长度为k的最长递增子序列，则为正无穷.
 求最大的x，使得不为正无穷。
 
这个新定义与原问题的等价性也不难证明，请读者体会一下。
 上述的就是状态，定义中的“为：在前i项中，长度为k的最长递增子序列中，最后一位的最小值”就是对状态的定义。
  
2. 什么是状态转移方程？
 
上述状态定义好之后，状态和状态之间的关系式，就叫做状态转移方程。
 
 比如，对于LIS问题，我们的第一种定义：
  
 
 设为：以数列中第k项结尾的最长递增子序列的长度.
 
设A为题中数列，状态转移方程为：
  
 
  （根据状态定义导出边界情况）
 
 
用文字解释一下是：
 以第k项结尾的LIS的长度是：保证第i项比第k项小的情况下，以第i项结尾的LIS长度加一的最大值，取遍i的所有值（i小于k）。
 
 第二种定义：
  
 
 设为：在数列前i项中，长度为k的递增子序列中，最后一位的最小值
 
设A为题中数列，状态转移方程为：
  
 
 若则
 否则：
 
（边界情况需要分类讨论较多，在此不列出，需要根据状态定义导出边界情况。）
 大家套着定义读一下公式就可以了，应该不难理解，就是有点绕。
 
 这里可以看出，这里的状态转移方程，就是定义了问题和子问题之间的关系。
 可以看出，状态转移方程就是带有条件的递推式。
  
3. 动态规划迷思
 
本题下其他用户的回答跟动态规划都有或多或少的联系，我也讲一下与本答案的联系。
 
 a. “缓存”，“重叠子问题”，“记忆化”：
 这三个名词，都是在阐述递推式求解的技巧。以Fibonacci数列为例，计算第100项的时候，需要计算第99项和98项；在计算第101项的时候，需要第100项和第99项，这时候你还需要重新计算第99项吗？不需要，你只需要在第一次计算的时候把它记下来就可以了。
 上述的需要再次计算的“第99项”，就叫“重叠子问题”。如果没有计算过，就按照递推式计算，如果计算过，直接使用，就像“缓存”一样，这种方法，叫做“记忆化”，这是递推式求解的技巧。这种技巧，通俗的说叫“花费空间来节省时间”。都不是动态规划的本质，不是动态规划的核心。
 
 b. “递归”：
 递归是递推式求解的方法，连技巧都算不上。
 
 c. "无后效性"，“最优子结构”：
 上述的状态转移方程中，等式右边不会用到下标大于左边i或者k的值，这是"无后效性"的通俗上的数学定义，符合这种定义的状态定义，我们可以说它具有“最优子结构”的性质，在动态规划中我们要做的，就是找到这种“最优子结构”。
 在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。对状态和“最优子结构”的关系的进一步解释，什么是动态规划？动态规划的意义是什么？ - 王勐的回答 写的很好，大家可以去读一下。
 
 需要注意的是，一个问题可能有多种不同的状态定义和状态转移方程定义，存在一个有后效性的定义，不代表该问题不适用动态规划。这也是其他几个答案中出现的逻辑误区：
 动态规划方法要寻找符合“最优子结构“的状态和状态转移方程的定义，在找到之后，这个问题就可以以“记忆化地求解递推式”的方法来解决。而寻找到的定义，才是动态规划的本质。
 
 有位答主说：
  
 
 分治在求解每个子问题的时候，都要进行一遍计算
 动态规划则存储了子问题的结果，查表时间为常数
 
这就像说多加辣椒的菜就叫川菜，多加酱油的菜就叫鲁菜一样，是存在误解的。
 
  
文艺的说，动态规划是寻找一种对问题的观察角度，让问题能够以递推（或者说分治）的方式去解决。寻找看问题的角度，才是动态规划中最耀眼的宝石！（大雾）
 

 
 
王勐动态规划的本质
 
 
 

 
 
 

        动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间
  。
 
       理解动态规划并不需要数学公式介入，只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是动态规划可以解决的，才能明白为神马需要动态规划。不过好处时顺便也就搞明白了递推贪心搜索和动规之间有什么关系，以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然熟悉了之后可以直接根据问题的描述得到思路，如果有需要的话再补充吧。
       动态规划是对于 某一类问题 的解决方法！！重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推！
 怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态（不要纠结硬盘之类的外部存储，就算考虑他们也只是扩大了状态的存储容量而已，并不能改变下一个状态只能从当前状态计算出来这一条铁律）
 
       当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！
       太抽象了还是举个例子吧：
       比如说我想计算第100个非波那契数，每一个非波那契数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数；每计算一个新状态所需要的时间也是常数且状态是线性递增的，所以时间复杂度也是线性的。
       上面这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行（a[i]=a[i-1]+a[i-2]），不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。
       非波那契那个例子过于简单，以至于让人忽视了阶段的概念，所谓阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。非波那契数列中，每一步会计算得到一个新数字，所以每个阶段只有一个状态。想象另外一个问题情景，假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。
 现在问题来了，有了阶段之后，计算新状态可能会遇到各种奇葩的情况，针对不同的情况，就需要不同的算法，下面就分情况来说明一下：
       假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。
       好消息是，有时候我们并不需要真的计算所有状态，比如这样一个弱智的棋盘问题：从棋盘的左上角到达右下角最短需要几步。答案很显然，用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态，正如这个问题中走n步可以走到很多位置一样。但是同样n步中，有哪些位置可以让我们在第n+1步中走的最远呢？没错，正是第n步中走的最远的位置。换成一句熟悉话叫做“下一步最优是从当前最优得到的”。所以为了计算最终的最优值，只需要存储每一步的最优值即可，解决符合这种性质的问题的算法就叫贪心。如果只看最优状态之间的计算过程是不是和非波那契数列的计算很像？所以计算的方法是递推。
 
       既然问题都是可以划分成阶段和状态。这样一来我们一下子解决了一大类问题：一个阶段的最优可以由前一个阶段的最优得到。
       如果一个阶段的最优无法用前一个阶段的最优得到呢？
       什么你说只需要之前两个阶段就可以得到当前最优？那跟只用之前一个阶段并没有本质区别。最麻烦的情况在于你需要之前所有的情况才行。
       再来一个迷宫的例子。在计算从起点到终点的最短路线时，你不能只保存当前阶段的状态，因为题目要求你最短，所以你必须知道之前走过的所有位置。因为即便你当前再的位置不变，之前的路线不同会影响你的之后走的路线。这时你需要保存的是之前每个阶段所经历的那个状态，根据这些信息才能计算出下一个状态！
 
       每个阶段的状态或许不多，但是每个状态都可以转移到下一阶段的多个状态，所以解的复杂度就是指数的，因此时间复杂度也是指数的。哦哦，刚刚提到的之前的路线会影响到下一步的选择，这个令人不开心的情况就叫做有后效性。
       刚刚的情况实在太普遍，解决方法实在太暴力(爆搜)，有没有哪些情况可以避免如此的暴力呢？
       契机就在于后效性。
       有一类问题，看似需要之前所有的状态，其实不用。不妨也是拿最长上升子序列的例子来说明为什么他不必需要暴力搜索，进而引出动态规划的思路。
 
       假装我们年幼无知想用搜索去寻找最长上升子序列。怎么搜索呢？需要从头到尾依次枚举是否选择当前的数字，每选定一个数字就要去看看是不是满足“上升”的性质，这里第i个阶段就是去思考是否要选择第i个数，第i个阶段有两个状态，分别是选和不选。哈哈，依稀出现了刚刚迷宫找路的影子！咦慢着，每次当我决定要选择当前数字的时候，只需要和之前选定的一个数字比较就行了！这是和之前迷宫问题的本质不同！这就可以纵容我们不需要记录之前所有的状态啊！既然我们的选择已经不受之前状态的组合的影响了，那时间复杂度自然也不是指数的了啊！虽然我们不在乎某序列之前都是什么元素，但我们还是需要这个序列的长度的。所以只需要记录以某个元素结尾的LIS长度就好！因此第i个阶段的最优解只是由前i-1个阶段的最优解得到的，然后就得到了DP方程（感谢@韩曦 指正）
  
  

   
   
 
  
 
  
<span style="font-size:18px;">#include <iostream>
using namespace std;

int lis(int A[], int n)
{
    int *d = new int[n];
    int len = 1;
    for(int i=0; i<n; ++i)
   {
        d[i] = 1;
        for(int j=0; j<i; ++j)
            if(A[j]<=A[i] && d[j]+1>d[i])
                d[i] = d[j] + 1;
        if(d[i]>len) len = d[i];
    }
    delete[] d;
    return len;
}
int main(){
    int A[] = {5, 3, 4, 8, 6, 7};
    cout<<lis(A, 6)<<endl;
    return 0;
}</span>
  该算法的时间复杂度是O(n^2 )，并不是最优的解法。还有一种很巧妙的算法可以将时间复杂度降到O(nlogn)，网上已经有各种文章介绍它，主要是维护一个上升序列表，然后对每一个新加入的数字尝试去二分插入。
 传送门：LIS的O(nlogn)解法。此题还可以用“排序+LCS”来解，感兴趣的话可自行Google。
 
 所以一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！
 
 每个阶段只有一个状态->递推；
 每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；
 每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；
 每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到这个性质叫做最优子结构；
 而不管之前这个状态是如何得到的，这个性质叫做无后效性。
 
 另：其实动态规划中的最优状态的说法容易产生误导，以为只需要计算最优状态就好，LIS问题确实如此，转移时只用到了每个阶段“选”的状态。但实际上有的问题往往需要对每个阶段的所有状态都算出一个最优值，然后根据这些最优值再来找最优状态。比如背包问题就需要对前i个包（阶段）容量为j时（状态）计算出最大价值。然后在最后一个阶段中的所有状态种找到最优值。
 
 
 
 
 
常见的动态规划问题分析与求解
 
五岳——算法设计手册常用算法归类
 
 
动态规划（Dynamic Programming，简称DP），虽然抽象后进行求解的思路并不复杂，但具体的形式千差万别，找出问题的子结构以及通过子结构重新构造最优解的过程很难统一，并不像回溯法具有解决绝大多数问题的银弹（全面解析回溯法：算法框架与问题求解)。为了解决动态规划问题，只能靠多练习、多思考了。本文主要是对一些常见的动态规划题目的收集，希望能有所帮助。难度评级受个人主观影响较大，仅供参考。
 
目录（点击跳转）
 
动态规划求解的一般思路
 
备忘录法
 
1.硬币找零
 
　　扩展1：单路取苹果
 
　　扩展2：装配线调度
 
2.字符串相似度/编辑距离（edit distance）
 
　　应用1：子串匹配
 
　　应用2：最长公共子序列
 
3.最长公共子序列(Longest Common Subsequence,lcs)
 
　　扩展1：输出所有lcs
 
　　扩展2：通过LCS获得最长递增自子序列
 
4.最长递增子序列（Longest Increasing Subsequence,lis）
 
　　扩展：求解lis的加速
 
5.最大连续子序列和/积
 
　　扩展1：正浮点数数组求最大连续子序列积
 
　　扩展2：任意浮点数数组求最大连续子序列积
 
6.矩阵链乘法
 
　　扩展：矩阵链乘法的备忘录解法（伪码）
 
7.0-1背包问题
 
8.有代价的最短路径
 
9.瓷砖覆盖（状态压缩DP）
 
10.工作量划分
 
11.三路取苹果
 
参考资料
 
附录1：其他的一些动态规划问题与解答（链接）
 
附录2：《算法设计手册》第八章 动态规划 面试题解答
 
动态规划求解的一般思路： 
 
　　判断问题的子结构（也可看作状态），当具有最优子结构时，动态规划可能适用。
 
　　求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。分治法则不同，每次递归都产生新的问题。
 
　　重新构造一个最优解。
 
备忘录法：
 
　　动态规划的一种变形，使用自顶向下的策略，更像递归算法。
 
　　初始化时表中填入一个特殊值表示待填入，当递归算法第一次遇到一个子问题时，计算并填表；以后每次遇到时只需返回以前填入的值。
 
　　实例可以参照矩阵链乘法部分。 
 
1.硬币找零
 
难度评级：★
 
　　假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。 
 
解法：
 
　　用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0...n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], ...)+1。对应于给定数目的找零total，需要求解sum[total]的值。
 
 
typedef struct {
    int nCoin; //使用硬币数量
    //以下两个成员是为了便于构造出求解过程的展示
    int lastSum;//上一个状态
    int addCoin;//从上一个状态达到当前状态所用的硬币种类
} state;
state *sum = malloc(sizeof(state)*(total+1));

//init
for(i=0;i<=total;i++) 
    sum[i].nCoin = INF;
sum[0].nCoin = 0;
sum[0].lastSum = 0;

for(i=1;i<=total;i++)
    for(j=0;j<n;j++)
        if(i-coin[j]>=0 && sum[i-coin[j]].nCoin+1<sum[i].nCoin)
        {
            sum[i].nCoin = sum[i-coin[j]].nCoin+1;
            sum[i].lastSum = j;
            sum[i].addCoin = coin[j];
        }

    if(sum[total].nCoin == INF) 
    {
        printf("can't make change.\n");
        return 0;
    }
    else
        //output
　　　　;
 
　　通过sum[total].lastSum和sum[total].addCoin，很容易通过循环逆序地或者编写递归调用的函数正序地输出从结束状态到开始状态使用的硬币种类。以下各题输出状态转换的方法同样，不再赘述。下面为了方便起见，有的题没有在构造子结构的解时记录状态转换，如果需要请类似地完成。
 
扩展：
 
(1)一个矩形区域被划分为N*M个小矩形格子，在格子(i,j)中有A[i][j]个苹果。现在从左上角的格子(1,1)出发，要求每次只能向右走一步或向下走一步，最后到达(N,M)，每经过一个格子就把其中的苹果全部拿走。请找出能拿到最多苹果数的路线。
 
难度评级：★
 
分析：
 
　　这道题中，当前位置(i,j)是状态，用M[i][j]来表示到达状态(i,j)所能得到的最多苹果数，那么M[i][j] = max(M[i-1][j],M[i][j-1]) + A[i][j] 。特殊情况是M[1][1]=A[1][1]，当i=1且j!=1时,M[i][j] = M[i][j-1] + A[i][j]；当i!=1且j=1时M[i][j] = M[i-1][j] + A[i][j]。
 
　　求解程序略。
 
(2)装配线调度（《算法导论》15.1）
 
难度评级：★
 
　　
 

 
 
 
2.字符串相似度/编辑距离（edit distance）
 
难度评级：★
 
　　对于序列S和T，它们之间距离定义为：对二者其一进行几次以下的操作(1)删去一个字符；(2)插入一个字符；(3)改变一个字符。每进行一次操作，计数增加1。将S和T变为同一个字符串的最小计数即为它们的距离。给出相应算法。
 
解法：
 
　　将S和T的长度分别记为len(S)和len(T)，并把S和T的距离记为m[len(S)][len(T)]，有以下几种情况：
 
       如果末尾字符相同，那么m[len(S)][len(T)]=m[len(S)-1][len(T)-1]；
 
       如果末尾字符不同，有以下处理方式
 
       修改S或T末尾字符使其与另一个一致来完成，m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1；
 
       在S末尾插入T末尾的字符，比较S[1...len(S)]和S[1...len(T)-1]；
 
       在T末尾插入S末尾的字符，比较S[1...len(S)-1]和S[1...len(T)]；
 
        删除S末尾的字符，比较S[1...len(S)-1]和S[1...len(T)]；
 
       删除T末尾的字符，比较S[1...len(S)]和S[1...len(T)-1]；
 
　　总结为，对于i>0,j>0的状态(i,j),m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)。
 
　　这里的重叠子结构是S[1...i]，T[1...j]。
 
　　以下是相应代码。考虑到C语言数组下标从0开始，做了一个转化将字符串后移一位。
 
#include <stdio.h>
#include <string.h>
#define MAXLEN 20
#define MATCH 0
#define INSERT 1
#define DELETE 2

typedef struct {
    int cost;
    int parent;
} cell;

cell m[MAXLEN+1][MAXLEN+1];

int match(char a,char b)
{
    //cost of match
    //match:    0
    //not match:1
    return (a==b)?0:1;
}

int string_compare(char *s,char *t)
{
    int i,j,k;
    int opt[3];
    
    //row_init(i);
    for(i=0;i<=MAXLEN;i++) {
        m[i][0].cost = i;
        if(i==0)
            m[i][0].parent = -1;
        else
            m[i][0].parent = INSERT;
    }

    //column_init(i);
    for(i=0;i<=MAXLEN;i++) {
        m[0][i].cost = i;
        if(i==0)
            continue;
        else
            m[0][i].parent = INSERT;
    }
    
    char m_s[MAXLEN+1] = " ",m_t[MAXLEN+1] =" ";
    strcat(m_s,s);
    strcat(m_t,t);

    for(i=1;i<=strlen(s);i++)
    {
        for(j=1;j<=strlen(t);j++) {
            opt[MATCH] = m[i-1][j-1].cost + match(m_s[i],m_t[j]);
            opt[INSERT] = m[i][j-1].cost + 1;
            opt[DELETE] = m[i-1][j].cost + 1;
            m[i][j].cost = opt[MATCH];
            m[i][j].parent = MATCH;
            for(k=INSERT;k<=DELETE;k++)
                if(opt[k]<m[i][j].cost)
                {
                    m[i][j].cost = opt[k];
                    m[i][j].parent = k;
                }
        }
    }
    i--,j--;
    //goal_cell(s,t,&i,&j);
    return m[i][j].cost;
}

int main() {
    char t[] = "you should not";
    char p[] = "thou shalt not";

    int n = string_compare(t,p);
    printf("%d\n",n);
}

字符串相似度/edit distance
 
应用：
 
　　(1)子串匹配
 
　　难度评级：★★
 
　　修改两处即可进行子串匹配：
 
row_init(int i)
{
    m[0][i].cost = 0; /* note change */
    m[0][i].parent = -1; /* note change */
}

goal_cell(char *s, char *t, int *i, int *j)
{
    int k; /* counter */
    *i = strlen(s) - 1;
    *j = 0;
    for (k=1; k<strlen(t); k++)
        if (m[*i][k].cost < m[*i][*j].cost) *j = k;
}

<span style="font-family:Microsoft YaHei;">修改部分</span>
 
如果j= strlen(S) - strlen(T)，那么说明T是S的一个子串。
 
　　（这部分是根据《算法设计手册》8.2.4和具体实例Skiena与Skienaa、Skiena与somta的分析获得的，解释不够全面，可能有误，请注意）
 
　　(2)最长公共子序列
 
　　难度评级：★★
 
　　将match时不匹配的代价转化为最大长度即可：
 
int match(char c, char d)
{
    if (c == d) return(0);
    else return(MAXLEN);
}
 
　　此时，最小值是两者不同部分的距离。
 
　　（这部分同样也不好理解，对于最长公共子序列，建议直接使用下一部分中的解法）
 
扩展：
 
　　如果在编辑距离中各个操作的代价不同，如何寻找最小代价？