动态规划思想

一、动态规划概念：

• 动态规划（dp）是研究多步决策过程最优化问题的一种数学方法。在动态规划中，为了寻找一个问题的最优解（即最优决策过程），将整个问题划分成若干个相应的阶段，并在每个阶段都根据先前所作出的决策作出当前阶段最优决策，进而得出整个问题的最优解。即记住已知问题的答案，在已知的答案的基础上解决未知的问题。

• 在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。可以自行创建一个动态规划表dp,dp一般是个数组，可以是一维也可以是二维数组，根据题中的需要，然后将子问题的最优解填入其中，方便在求解之后的子问题时可以方便调用，进而求出整个问题的最优解。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

• 动态规划有两种实现方法，一种是递推，另一种是记忆化搜索。两种方法时间复杂度完全相同，但是，递推的效率要比记忆化搜索高不少，而且以后的大量优化技巧都建立在递推上（滚动数组、单调队列、斜率优化……）。所以，我们一般用递推来写动态规划。

二、动态规划的性质：

(1) 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

(2) 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

三、动规解题的一般思路：

动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤。

初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态

(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。

四、解题步骤：

• 拆分问题；

• 定义状态并找出初状态；

• 状态转移方程。

五、算法实现的步骤：

1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述

2、找到初始条件，设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。

3、根据初始条件或边界条件，找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。

4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。

六、例题

应用举例1：

题目描述：超级台阶

题目描述
有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

注：规定从一级到一级有0种走法。

输入格式
输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40), 表示楼梯的级数。

输出格式
对于每个测试实例，请输出不同走法的数量。

输入输出样例
输入

2
2
3
输出

1
2

代码思路：

首先考虑题中要求的是走上m级台阶总共有多少走法，不妨设dp(m) = ans;
再考虑下子问题：
dp(m-1) 就是走上m-1级台阶总共有多少走法
dp(m-2)就是走上m-2级台阶总共有多少走法
子问题与原问题的关系：题中告诉我们每次只可以跨一级或两级，那么反过来理解就是，第m级台阶可能是m-1或者m-2级台阶走上来的，如果已经求出了dp(m-1)和dp(m-2),很明显：
dp(m) = dp(m-1)+dp(m-2);

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iluDfX2P-1631356231751)(C:\Users\86152\AppData\Roaming\Typora\typora-user-images\image-20210911151227624.png)]

代码实现：

#include "iostream"
using namespace std;
int n;
int m,dp[3];//创建dp数组，之用来存储三级台阶
int main(){
    cin>>n;
    for (int i = 1; i <=n ; ++i) {
        cin>>m;
        dp[0] = dp[1] = 1; // 初始化第一、二级台阶为1，这样之后的可以递推
        if(m<2){ 
            break;
        }
        for(int j=2;j<m;j++){ //从第二级开始递推
            dp[j%3] = dp[(j-1)%3]+dp[(j-2)%3];//这里使用滚动数组来优化空间
        }
        cout<<dp[(m-1)%3]<<endl;
    }
    return 0;
}

应用举例2：

题目描述：矩阵最短路径

给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和，如果给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.

1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0

代码思路：

​ 由分析可知：走到第(i ,j)个数时，只可能是从(i-1 ,j)或是(i ,j-1)走来的，路径(i ,j)的阶段依赖的是(i-1 ,j)和(i ,j-1)的子阶段，所以状态转移方程为

dp[i][j] =a[i][j] + min(dp[i-1][j]+ dp[i][j-1])

，属于简单的动态规划问题。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-U6B1k1uq-1631356231756)(C:\Users\86152\AppData\Roaming\Typora\typora-user-images\image-20210911151251206.png)]

代码实现：

#include <iostream>
#include <algorithm>
using namespace std;
int dp[4][4] = {};     //全局数组，存放决策表
int main()
{
	int a[4][4] = {1,3,5,9,8,1,3,4,5,0,6,1,8,8,4,0};  //矩阵存储a[i][j]
	for (int i = 0;i < 4;++i){
		for (int j = 0;j < 4;++j){
			if (i==0 && j==0){//第一个初始为自身，边界条件问题需要考虑到
				dp[i][j] = a[i][j];
			} 
			else if (i==0 && j!=0){ //如果是第一行的，只能从左边过来
				dp[i][j] = a[i][j] + dp[i][j-1];
			}
			else if (i!=0 && j==0){ //如果是第一列的只能从上边下来
				dp[i][j] = a[i][j] + dp[i-1][j];
			}
			else{ //其他情况下，就要取 从上边下来或者从左边做来 这两种中的最小值
				dp[i][j] = a[i][j] + min(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout<<"走到位置"<<"(4,4)"<<"最短路径为：";
	cout<<dp[3][3]<<endl;    
	return 0;
}

应用举例3：

问题描述：最长递增子序列

给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5。

思路分析：

首先生成dp[n]的数组，dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说，很明显dp[0]为1，当我们计算dp[i]的时候，我们去考察i位置之前的所有位置，找到i位置之前的最大的dp值，记为dpj,dp[j]代表以arr[j]结尾的最长递增序列，而dp[j]又是之前计算过的最大的那个值，我们在来判断arr[i]是否大于arr[j],如果大于dp[i]=dp[j]+1.计算完dp之后，我们找出dp中的最大值，即为这个串的最长递增序列。

应用举例4：导弹拦截

题目描述：

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹的枚数和导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，每个数据之间有一个空格）。
计算这套系统最多能拦截多少导弹？

【输入格式】
第一行，数字n表示n个导弹(n<=200)
第二行，n个数字，表示n个导弹的高度
【输出格式】
第一行，一个整数，表示最多能拦截的导弹数
【样例数据】
input：

8
389 207 155 300 299 170 158 65
output：

6

思路分析：

首先我们需要选择一个点，作为你要拦截的那串导弹的终点（为什么是找终点而不是找起点呢？可以通过“无后效性”分析得知，选择终点可以利用前边那些点的最优决策。
用一个数组f[i]表示拦截到底i颗导弹时已经拦截几个了，如果第j个导弹比第i个导弹低，就说明前面肯定没有拦截到第j个。我们可以枚举1～i-1这些导弹，选择一个f数值最大的，把第i个导弹作为它的后缀，也就是说：f[i]=max{f[j]}+1;1<=j<i；

代码展示：

int a[50000],f[50000];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
 	   cin>>a[i];   //高度数组
	int ans=0; //最大拦截数
    for(int i=1;i<=n;i++){
        f[i]=1; // f数组都初始化1，即自身一定可以拦截
        for(int j=1;j<i;j++) //从选择的那个点之前的点开始遍历
            if(a[i]<=a[j])  //如果终点前边有比终点高的，就说明终点可以被再次拦截
				f[i]=max(f[i],f[j]+1); //需要考虑的是有可能前边有好几个点都符合，那么就要选最大的
        ans=max(ans,f[i]);//将每个点的最终状态都进行比较，取最大值，就是最大拦截数
    }
    cout<<ans<<endl;

应用举例5：数组最大连续子序列和

题目描述：

如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就是最大值。越加越大。

应用举例6：两个字符串最大公共子序列

思路分析：

有两个字符串s1，s2，我们用dp[][][i][j]表示s1中前i个字符与s2中前j个字符分别组成的两个前缀字符串的最长公共子串的长度。当i或j等于0时，我们可以直接得到结果等于0.用两个for循环代表s1长度为i，s2长度为j时他们的最大子序列dp[i][j]。

若s1[i]=s2[j]，由于他们都是各自子串的最后一个字符，所以必定存在一个最大子串有这个字符结尾，其他部分和 i-1、 j-1时的子串相同。

dp[i][j]=dp[i-1][j-1]+1;

相反的如果不同，那么就需要比较是s1中前i-1个字符和s2中j个字符的最大子串长还是s1中前i个字符和s2中j-1个字符的最大字串长。

dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

重点在于每次比较的是原来s1和s2的不同长度的子串，然后再依次往后推移，直到整个字符串都遍历。

代码展示：

int MaxTwoArraySameOrderMethod(string str1, string str2) {
	int m = str1.length();
	int n = str2.length();
	/*
	 * 定义一个二维数组保存公共子序列长度
	 * dp[i][j]表示字符串1从头开始长度是i，字符串2从头开始长度是j，这两个字符串的最长公共子序列的长度
	 * 设置数组行列比他们长度大一往二维数组中填写数字时，每个位置的数字跟他上方或者左方或者左上方数字有关系，这样处理边界数字时不用处理这种情况，方便接下来的循环
	 */
	int dp[m+1][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]时长度最大的再加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];
}

应用举例7：0-1背包问题

题目描述：

在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数），求背包能够容纳的最大价值。

思路分析：

动态规划，创建一个二维数组dp，来存储每种情况下的最大价值。横坐标为物品的个数从0-n,纵坐标为容量从0-w，可以知道无论是物品数为0，还是容量为0，价值都是0，可以作为起始条件。

对每个容量去分析这些物品哪些能放进去，总共能放进去几个，如果能放进去，需要考虑放不放，放的话价值变为 dp[i][j-w[i]]+p[i]（意思就是放同样的个数之前那个容量能放的再加上现在这个），如果能放但不放，价值和dp[i-1][j]（容量一样，但个数少一个）一样，取这两个中较大。

如果不能放，同样是dp[i-1][j]。

代码展示：

int PackageHelper(int n, int w[], int p[], int v) {
        // n物品个数，w体积，p价值，v容量
	//设置一个二维数组，横坐标代表从第一个物品开始放到第几个物品，纵坐标代表背包还有多少容量，dp代表最大价值
 	int dp[n+1,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];
}

应用举例8：找零钱问题

问题描述：

有数组penny，penny中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim(小于等于1000)代表要找的钱数，求换钱有多少种方法。给定数组penny及它的大小(小于等于50)，同时给定一个整数aim，请返回有多少种方法可以凑成aim。

思路分析：

   设dp[i][j]代表钱为j，i纸币的面值时共有的找钱方法。先找到每种面值的解决方法，然后递推，逐步再求出所有面值都有的时候的找钱方法。
   如果钱j为0，那么方法肯定为0。如果钱数是第一种纸币的面值的整数倍，那么只有1种方法，或者0种方法，这是初始条件。
   之后对钱和面值开始遍历，如果钱数大于面值（证明可以找零钱），那么方法数= 面值是前边一种，钱数不变的的时候的方法  +   面值不变，钱数=钱数-面值 时的方法（dp[i][j] = dp[i - 1][j] + dp[i][j - penny[i]]）。因为，对于某种面值我们有两种情况，用或不用，不用就是dp[i - 1][j]  ，用了，那么此时的钱就必须先减取面值，j-penny[i]，所以是dp[i][j - penny[i]]。至于考虑用的张数，这个会在遍历钱j的时候考虑到。

int countWays(int penny[], int n, int aim) {
              //penny 面值数组， 面值个数，aim 总钱数
 	int dp[n][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];
}