总结015—dp

这周开始练习dp，dp是用来解决最优化问题的思想，一般可以解决重叠子问题和最优子结构看文章中的题时，每道题虽然代码量少，但是其中的状态转移方程是真不容易想到。如何设计状态和状态转移方程是动态规划的核心。

下面举几个经典和较难想到状态的案例

1、最大连续子序列和(题意如题名) 状态转移方程dp[i]=max{A[i],dp[i-1]+A[i]}，给出状态转移方程那么代码就很容易写出了。

2、最长公共子序列（LCS） 问题描述：给定两个字符串（或数字序列）A和B，求一个字符串，使得这个字符串是A和B的最长公共部分（子序列可以不连续）。

令dp[i][j]表示字符串A的i号位和字符串B的j号位之前的LCS长度（下标从1开始），根据A[i]和B[j]的情况分为两种决策。A[i]==B[j]时状态转移方程：dp[i][j]=dp[i-1][j-1]+1;;;A[i]!=B[j]时状态转移方程：dp[i][j]=max{dp[i][j-1],dp[i-1][j]}。状态转移方程代码如下：

//状态转移方程 
	for(int i=1;i<=lenA;i++)
	{
		for(int j=1;j<=lenB;j++)
		{
			if(A[i]==B[j])
			{
				dp[i][j]=dp[i-1][j-1]+1;
			}
			else
			{
				dp[i][j]=max{dp[i-1][j],dp[i][j-1]};
			}
		}
	}

 3、最大子矩阵和​​​​​​

状态转移方程处代码

//状态转移方程 
	for(int i=1;i<=m;i++)//列 
	{
		for(int j=i;j<=m;j++)//列 
		{
			int cur=0;
			for(int k=1;k<=n;k++)//行 
			{
				sum[k] = i==j?a[k][j]:sum[k]+a[k][j];
				cur+=sum[k];//从左上到右下 
				if(cur<0)cur=0;
				ans=max(ans,cur);//保存大的矩阵和 
			} 
		}
	}
	cout<

4、01背包问题

有n件物品，每件物品的重量为w[i],价值为c[i]。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。（每个物品只有一件）

第i件只有放与不放两种选择，如果不放则问题转化为前i-1件物品恰好装入容量为v的背包所能获得的最大价值，即dp[i-1][v];如果放则问题转化为前i-1件物品恰好装入容量为v-w[i]的背包所能获得的最大价值，即dp[i-1][v-w[i]]+c[i];状态转移方程：dp[i][v]=max{dp[i-1][v],dp[i-1][v-w[i]]+c[i]}(1<=i<=n,w[i]<=v<=V);用一维数组来写为：dp[v]=max{dp[v],dp[v-w[i]]+c[i]}(1<=i<=n,w[i]<=v<=V)；代码如下

//状态转移方程 二维 
	for(int i=1;i<=n;i++)
	{
		for(int v=w[i];v<=V;v++)//v的枚举顺序还是逆序都可以 
		{
			dp[i][v]=max(dp[i-1][v],dp[i-1][v-w[i]]+c[i]);
		}
	} 
	
//状态转移方程 一维
	for(int i=1;i<=n;i++)
	{
		for(int v=V;v>=w[i];v--)//v的枚举必须逆序 
		{
			dp[v]=max{dp[v],dp[v-w[i]]+c[i]};
		}
	} 

总结：只要把状态转移方程搞懂搞会，那么这道题基本就算解决了。这周大部分时间都是在思考每道题的状态转移，同时感觉每道题也有一些相似的程度。