本文对原博客做了少量修改，包括个别错误的地方。代码改为了c++实现，原文使用的Java。
已知问题规模为n的前提A，求解一个未知解B。（我们用An表示“问题规模为n的已知条件”）
此时，如果把问题规模降到0，即已知A0，可以得到A0->B.
如果从A0添加一个元素，得到A1的变化过程。即A0->A1; 进而有A1->A2; A2->A3; …… ; Ai->Ai+1. 这就是严格的归纳推理，也就是我们经常使用的数学归纳法；
对于Ai+1，只需要它的上一个状态Ai即可完成整个推理过程（而不需要更前序的状态）。我们将这一模型称为马尔科夫模型。对应的推理过程叫做“贪心法”。
然而，Ai与Ai+1往往不是互为充要条件，随着i的增加，有价值的前提信息越来越少，我们无法仅仅通过上一个状态得到下一个状态，因此可以采用如下方案：
{A1->A2}; {A1, A2->A3}; {A1,A2,A3->A4};……; {A1,A2,...,Ai}->Ai+1.
这种方式就是第二数学归纳法。对于Ai+1需要前面的所有前序状态才能完成推理过程。我们将这一模型称为高阶马尔科夫模型。对应的推理过程叫做“动态规划法”。
举个通俗易懂的例子，动态规划像递归和贪心算法一样，是解决一类问题的方法。要理解动态规划，可以拿它与递归算法作对比。我们以计算斐波那契数列第n项值A为例，递归算法是直接计算A=A+A，然后递归计算A和A。而动态规划则是从A开始，依次计算A、A直到A，不管子问题是否用到都进行计算，并且只计算一次。
递归就是直接计算结果，需要前面什么子问题就去计算那个子问题，可能多次计算同一个子问题。动态规划则是不管是否用到，先把前面子问题计算依次出来，每个子问题只计算一次。递归算法：
int sol_Fibonacci(int n) { if(n == 0){ return 0; } else if(n == 1){ return 1; } else { return sol_Fibonacci(n-1)+sol_Fibonacci(n-2); } }动态规划：
int sol_Fibonacci(int n) { if (n == 0) { return 0; } else if (n == 1) { return 1; } else { int* result = new int[n]; result[0] = 0; result[1] = 1; for (int i = 2; i <= n; ++i) { result[i] = result[i - 1] + result[i - 2]; } int t=result[n]; delete[] result; return t; } }从这个例子中表面上好像看不出它们的差距，但是仔细一想，在递归算法中，A被计算了两次，分别是计算A和A的时候递归调用了，可能你这个时候还以为计算次数是2倍的关系，但是你要知道A所调用的A和A将被计算更多遍，这里面是一个指数增长的过程。在计算斐波那契数列第10项值的时候，如果我们用递归算法，sol_Fibonacci这个函数将会被调用177次，如果计算第20项的值，sol_Fibonacci函数将会被调用21891次。而动态规划算法，则不需要反复计算前面步骤的值，这也是动态规划的优势。
能采用动态规划求解的问题的一般要具有3个性质：
(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
动规解题的一般思路 动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解。
算法实现的步骤
1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述
2、设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。
3、找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。
4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。代码基本框架：
arr[] = {3,1,4,1,5,9,2,6,5}的最长递增子序列长度为4。即为：1,4,5,9。
思路：设置一个数组temp，长度为原数组长度，数组第i个位置上的数字代表0...i上以arry[i]结尾的最长递增子序列。当增加一个数字时，最大递增子序列可能变成前面最大的递增子序列+1，也可能就是前面最大递增子序列，这需要让新增加进来的数字arr[i]跟前面所有数字比较大小，即当 arr[i] > arr[j]，temp[i] = max{temp[j]}+1。最后取最大的temp[i]即为最长递增子序列长度。
代码实现：
int MaxChildArrayOrder(int a[],int n) { int *temp = new int[n];//temp[i]代表以a[i]结尾的最长递增子序列 for (int i = 0; i < n; ++i) { temp[i] = 1;//初始值都为1 } for (int i = 1; i < n; ++i) { for (int j = 0; j < i; ++j) { if (a[i] > a[j] && temp[j] + 1 > temp[i]) { //如果有a[i]比它前面所有的数都大，则temp[i]为它前面的比它小的数的那一个temp+1取得的最大值 temp[i] = temp[j] + 1; } } } int max = temp[8]; //从temp数组里取出最大的值 for (int i = 1; i < n; ++i) { if (temp[i] > max) { max = temp[i]; } } return max; }如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就是最大值。 代码实现：
int MaxContinueArraySum(int a[],int n) { int my_max = a[0]; int sum = a[0]; for (int i = 1; i < n; ++i) { sum = max(sum + a[i], a[i]); if (sum >= my_max) { my_max = sum; } } return my_max; }数字塔是第i行有i个数字组成，从上往下每个数字只能走到他正下方数字或者正右方数字，求数字塔从上到下所有路径中和最大的路径，如有下数字塔
3
1 5
8 4 3
2 6 7 9
6 2 3 5 1
最大路径是3-5-3-9-5，和为25。我们可以分别从从上往下看跟从下往上看两种动态规划的方式去解这个题从上往下看：当从上往下看时，每进来新的一行，新的一行每个元素只能选择他正上方或者左左方的元素，也就是说，第一个元素只能连他上方的元素，最后一个元素只能连他左上方的元素，其他元素可以有两种选择，所以需要选择加起来更大的那一个数字，并把这个位置上的数字改成相应的路径值，具体过程如下图所示 3 3 3 3
1 5 4 8 4 8 4 8
8 4 3 8 4 3 12 12 11 12 12 11
2 6 7 9 2 6 7 9 2 6 7 9 14 18 19 20
6 2 3 5 1 6 2 3 5 1 6 2 3 5 1 20 20 22 25 21
具体运算过程就是，建立一个n*n的二维数组dp[][]，n是数字塔最后一行的数字个数，二维数组每一行数字跟数字塔每一行数字个数一样，保存的值是从上方到这一个位置最大路径的值，填入边界值dp[0][0]=3，每一行除了第一个值跟最后一个值，其他的值选择上方或者左上方更大的值与这个位置上的值相加得来的值，即dp[i][j]=max(dp[i-1][j-1], dp[i-1][j]) + n[i][j]。
int minNumberInRotateArray(int** n,int k) {//这里传入动态二维数组类型为int**，静态数组则为int n[5][5] int max = 0; int **dp = new int*[k]; for (int j = 0; j < k; j++) { dp[j] = new int[k]; } dp[0][0] = n[0][0]; for (int i = 1; i < k; i++) { for (int j = 0; j <= i; j++) { if (j == 0) { //如果是第一列，直接跟他上面数字相加 dp[i][j] = dp[i - 1][j] + n[i][j]; } else { //如果不是第一列，比较他上面跟上面左面数字谁大，谁大就跟谁相加，放到这个位置 dp[i][j] = (dp[i - 1][j - 1] > dp[i - 1][j] ) ? (dp[i - 1][j - 1]+n[i][j]) : (dp[i - 1][j] + n[i][j]); } max = (dp[i][j] > max) ? dp[i][j] : max;//也可以使用max=std::max(dp[i][j],max),因为我们这里定义了int max，所以要加std：： } } return max; }优化：可以使用以为数组代替二维数组，后面一行计算值直接覆盖前一行计算值。不过这时每一行要从有往左计算。因为每一行数会用到左上角值，即前一行的左边的值。
int minNumberInRotateArray2(int **n,int k) { int* temp = new int[k]; temp[0] = n[0][0]; for (int i = 1; i < k; ++i) { for (int j = i; j >= 0; --j) { if (j == i) { temp[i] = temp[i - 1] + n[i][j]; } else if (j == 0) { temp[0] += n[i][0]; } else { temp[j] = max(temp[j], temp[j - 1]) + n[i][j]; } } } int max = temp[0]; //从temp数组里取出最大的值 for (int i = 1; i < k; ++i) { if (temp[i] > max) { max = temp[i]; } } return max; }从下往上看时：从下往上看时大体思路跟从上往下看一样，但是要简单一些，因为不用考虑边界数据，从下往上看时，每进来上面一行，上面一行每个数字有两条路径到达下面一行，所以选一条最大的就可以。具体做法如上。
3 3 3 25
1 5 1 5 1 5 18 22
8 4 3 8 4 3 17 16 17 17 16 17
2 6 7 9 8 9 12 14 8 9 12 14 8 9 12 14
6 2 3 5 1 6 2 3 5 1 6 2 3 5 1 6 2 3 5 1
具体思想：设 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] =max(dp[i][j-1], dp[i-1][j])。最后二维数组最右下角的值就是最大子串。
代码如下：
int MaxTwoArraySameOrderMethod(string str1, string str2) { int m = str1.length(); int n = str2.length(); /* * 定义一个二维数组保存公共子序列长度 * dp[i][j]表示字符串1从头开始长度是i，字符串2从头开始长度是j，这两个字符串的最长公共子序列的长度 * 设置数组行列比他们长度大一往二维数组中填写数字时，每个位置的数字跟他上方或者左方或者左上方数字有关系，这样处理边界数字时不用处理这种情况，方便接下来的循环 */ int **dp = new int*[m + 1]; for (int i = 0; i < n + 1; i++) { dp[i] = new int[n + 1]; } /* * 初始化第一行第一列 * dp[0,j]表示啥？表示字符串1的长度是0，字符串2的长度是j，这两个字符串的最长公共子序列的长度是0，因为，字符串1 根本就没有嘛 */ for (int i = 0; i <= m; i++) { dp[i][0] = 0; } for (int i = 0; i <= n; i++) { dp[0][i] = 0; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { /* * 如果当c[i][j]时，字符串1从头开始长度是i，字符串2从头开始长度是j时他们最后一个字符相同 * 就同时把他们向前移动一位，找c[i-1][j-1]时长度最大的再加一 * 表现在二维数组中就是c[i][j]左上方的点 */ if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; /* * 如果当c[i][j]时，他们最后一个字符不相同 * 要将str1往前移动一位的c[i-1][j]的lcs长度，或者将str2往前移动一位的c[i][j-1]的lcs长度 * 哪个长，将它赋给c[i][j] * 表现在二维数组中就是c[i][j]上方的点或者左方的点 */ } else { dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } } return dp[m][n]; }在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] = max(dp[i-1][j], dp[i][j-w[i]]+p[i])；放不下，dp[i][j] = dp[i-1][j]；
int PackageHelper(int n, int w[], int p[], int v) { //w[]和p[]长度为n，dp[][]长度为(n+1)*(v+1) //设置一个二维数组，横坐标代表从第一个物品开始放到第几个物品，纵坐标代表背包还有多少容量，dp代表最大价值 int **dp = new int*[n + 1]; for (int i = 0; i < n + 1;i++) { dp[i] = new int[v + 1]; } for (int i = 0; i < n + 1; i++) { dp[i][0] = 0; } for (int i = 0; i < v + 1; i++) { dp[0][i] = 0; } for (int i = 1; i < n + 1; i++) { for (int j = 1; j < v+1; j++) { if (j >= w[i-1]) { /* * 当能放得下这个物品时，放下这个物品，价值增加，但是空间减小，最大价值是dp[i-1][j-w[i]]+p[i] * 当不放这个物品时，空间大，物品还是到i-1，最大价值是dp[i-1][j] * 比较这两个大小，取最大的，就是dp[i][j] */ dp[i][j] = max(dp[i - 1][j], dp[i ][j - w[i-1]] + p[i-1]); } else { //如果放不下，就是放上一个物品时的dp dp[i][j] = dp[i - 1][j]; } } } return dp[n][v]; }题目：
有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。
我们设dp[i][j]表示钱为j，且货币为penny[0...i]种时，共有的找钱方式。对于任意的一个值dp[i][j]表示使用arr[0~i]的元素来拼凑出目标值为j的方案数目，总结规律可以发现：dp[i][j]=dp[i-1][j]+dp[i-1][j-arr[i]]+dp[i-1][j-arr[i]*2]+……即arr[i]选0,1,2，...个时的情况。不难发现dp[i-1][j-arr[i]]+dp[i-1][j-arr[i]*2]的计算结果就是dp[i][j-arr[i]]的计算结果，于是dp[i][j]= dp[i-1][j]+ dp[i][j-arr[i]]。
代码如下：
int countWays(int penny[], int n, int aim) { // write code here int** dp = new int*[n]; for (int i = 0; i < n; i++) { dp[i] = new int[aim + 1]; } //初始状态 for (int i = 0; i < n; i++) dp[i][0] = 1;//aim=0时 for (int j = 1; j <= aim; j++) {//第一行 int i = penny[0]; if (j%i == 0) dp[0][j] = 1; else dp[0][j] = 0; } //从上到下 从左到右 for (int i = 1; i < n; i++) { for (int j = 1; j <= aim; j++) { if (j >= penny[i]) {//在前i-1项里面拼凑j，和在前i项里拼凑j-penny[i]--默认已经选择一个i dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n - 1][aim]; }用一维数组代替二维数组：
int countWays(int penny[], int n, int aim) { int* dp = new int[aim + 1];//表示每种钱数j有多少种拼凑情况 for (int j = 0; j <= aim; j++) {//初始 if (j%penny[0] == 0) dp[j] = 1; else dp[j] = 0; } for (int i = 1; i < n; i++) { for (int j = 1; j <= aim; j++) { if (j >= penny[i]) dp[j] = dp[j - penny[i]] + dp[j]; } } return dp[aim]; }
———————————————— 版权声明：本文为博主「zw6161080123」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。 原文链接：https://blog.csdn.net/zw6161080123/article/details/80639932
