1. 动态规划概念 [1]
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线．这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法
2. 基本思想 [2]
动态规划的基本思想是把原问题分解成子问题进行求解,先求解子问题，然后从这些子问题的解得到原问题的解。为了避免子问题重复，我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。
3. 适用条件 [3]
动态规划一般是自顶向下思考，自底向上实现的，适用动态规划的问题必须满足最优化原理和无后效性 。
1、最优化原理（最优子结构性质）
最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2、无后效性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性 。
3、子问题的重叠性
动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间 。
4.经典模型
斐波那契数列：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）
5. 应用实例
1. 问题描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
2. 问题分析
我下面所说的子段：被绳子被剪成的每一段都称为子段。
不可再减子段：无论怎么剪，该子段的子段长度乘积都无法达到绳子本身的长度。
由题可知绳子的长度最小为2，当绳子的长度为2时，只有一种剪法（1和1）乘积为1，当绳子的长度为3时，也只有一种剪法（1和2）乘积为2，当绳子的长度为4时，有两种剪法（1和3、2和2）且最大乘积为4，当绳子的长度为5时，有两种剪法（1和4、2和3）且最大乘积为6...
由此递推可以看出当绳子的长度为2或3时，无论怎么剪，子段的乘积都无法达到绳子本身的长度，而当绳子的长度不断增加，总有一种剪法可以使子段长度乘积等于或超过本身长度，所以2和3为不可再剪子段，其中3为最大不可再剪子段。用动态规划算法解决剪绳子问题的思路为：
自顶向下思考：要计算一条绳子子段的最大乘积m，可以把这条绳子分两个子段a和b，分别计算a和b的子段最大乘积m1和m2，再把这两个乘积相乘，由于这a和b的取值有多种情况，所以m1和m2的乘积也有多种情况，最大的那个即为我们要求的最终结果m。的那么这就需我们先分别求a的所有可能取值的子段最大乘积，和b的所有可能取值的子段最大乘积，求法同上，即把a剪成两段c和d，分别计算c和d的子段最大乘积m3和m4，再把这两个乘积相乘，由于这c和d的取值有多种情况，所以m3和m4的乘积也有多种情况，最大的那个即为我们要求的结果m1。b也同理，剪成两段e和f，分别计算e和f的子段最大乘积m5和m6，再把这两个乘积相乘，由于这e和f的取值有多种情况，所以m5和m6的乘积也有多种情况，最大的那个即为我们要求的结果m2。然后就需我们先分别求c，d，e，f的所有可能取值的子段最大乘积，所以再把c，d，e，f分为两段...以此类推不断分下去，直到分到长度为3或3以下，不可再分，因为切了乘积反而会变小。所以这道题的子问题为，求m1，m2，m3，m4，m4，m6......
自底向上实现：因为子段长度为1，2，3时都不可再切，切了乘积反而会变小，所以要求的m值即为自身长度。因此从子段长度为4开始递推，计算子段长度为5，6，7，8，9......时子问题的解（即为该子段的子段的最大乘积），一直递推到子段长度等于目标绳长，这时的结果即为我们要求的结果
3. 代码实现
#include <iostream>
#include <cmath>
using namespace std;
int maxProductOfCuttingRope(int length) {
if(length < 2)//不满足n>1
return 0;
if(length == 2)//绳子长度为2时,结果为1
return 1;
if(length == 3)//绳子长度为3时,结果为2
return 2;
//绳子长度大于等于4时，新建一个表用于储存子问题的解
int* m = new int[length + 1];
//子段长度小于4时子问题的解
m[0] = 0;
m[1] = 1;
m[2] = 2;
m[3] = 3;
//外层循环为：从子子段长度为4开始递推求子问题的解（即为m[i]），一直到子段长度等于绳长（i=length），这时的m[length]即为最终结果
for(int i = 4; i <= length; ++i) {
int max = 0; //i改变 ，对应的max值重置为0
//内层循环为：当子段长度为i时，把子段分为两段长度为j和i-j，求m[j]和m[i-j]的乘积记为product，j取不同值时product的最大值即m[i]，
//j的值以1为单位递增，以 j = i / 2 为界，当 j > i / 2 时分割方案和前面都是重复的，例如i=7时，分割方案有（1，6）（2，5）（3，4）这三种，从（4，3）开始就是重复的了。
for(int j = 1; j <= i / 2; ++j) {
int product = m[j] * m[i - j]; //计算当前j值下m[j]和m[i-j]的乘积product
//求j取不同值时product的最大值记为max
if(max < product)
max = product;
}
m[i] = max;//j取不同值时product的最大值max即为m[i]
}
int result = m[length];//记录结果，以免下面被销毁
delete[] m;//销毁打表的辅助空间
return result; //返回结果
}
int main(){
cout<<maxProductOfCuttingRope(8)<<endl;
return 0;
}
感谢阅读，如有问题欢迎指正！
[1][2][3] 引用自百度百科
