学步园

动态规划的经典题型：

1.最大连续和

2.最大子矩阵和

最后几个例题：hdu1003 模板题

                       poj1050=hdu1081

最大连续和：

最大连续和指的是对于一个一维数组，我们要求出其中 i 到 j 个连续的元素和最大，如(6,-1,5,4,-7),最大连续和为14，是第1个到第4个元素之和，那么对于这样一个问题，我们可以这样处理：

设 ans 为最后的最大和，初始化为负无穷大，x,y为我们ans最大的时候的区间(有的题目中不要用到)，初始化都为1，flag用来指示寻找最大和区间的左端点，初始化为1，sum表示寻找过程中的中间值，初始化为0，那么我们从数组第一位开始

sum += a[i];  那么如果 sum>ans ，就可以把ans更新为sum，并且区间更新 x = flag, y = i ; 这里之所以要对x更新，是因为，对于sum>ans判断之后，我们应该还有一个判断，如果sum<0; 那么我们的sum更新为 0，此时flag 更新为i+1，为什么要这样呢？如果当前的 i 点之后还出现有一个区间的sum > ans，那么 我们的区间x就可以靠flag，更新啦 ， 下面是模板：

for(i=0;i<N;i++)
    scanf("%d",&a[i]);

int x = 1,y = 1;
int flag = 1;
int sum = 0;
int ans = -INF;
for(int i = 1;i <= N;i ++)
{
	sum += a[i];
	if(sum > ans)
	{
		ans = sum;
		x = flag;
		y = i;
	}
	if(sum < 0)//这里 不能是else 要考虑所有数为负数
	{
		sum = 0;flag = i+1;
	}
}

最大子矩阵和：

 对于一维数组的连续和比较简单，那么对于一个二维的矩阵，怎么样求解其中一块小的子矩阵的最大和呢？

其实对于二维数组，我们只要把它转化为一维数组就可以啦，那么怎么转化，结合代码理解：

int temp[MAX],map[MAX][MAX];
int getsum()
{
	int sum = 0,max = -INF;
	for(int i = 1;i <= M; i ++)
	{
		sum += temp[i];
		if(sum > max) max = sum;
		if(sum < 0) sum = 0;
	}
	return max;
}
int main()
{
	for(int i = 1;i <= N; i ++)
		for(int j = 1;j <= M; j ++)
			scanf("%d",&map[i][j]);

	int ans = -INF;
	for(int i = 1; i <= N; i ++)//从第i行开始
	{
		memset(temp,0,sizeof(temp));
		for(int j = i; j <= N; j ++)//从i行到N行都尝试叠加上去
		{
			for(int k = 1; k <= M; k ++)//把i到j行的每一列加起来。。。就是矩阵压缩
				temp[k] += map[j][k];

			int pre = getsum();//计算压缩的一维连续区间最大和
			if(ans < pre)
				ans = pre;
		}
	}
	return 0;
}

对于一个N*M的矩阵，我们对于每一行进行所谓的矩阵压缩，就是对于第 i 行，借助一个temp数组，我们用一个for循环，把第i 到 N 行都叠加到这个一维数组上(矩阵压缩)，每次叠加一行，就对这个temp求一次区间最大，那么，整个程序完了之后，我们的ans就得到啦

最后 附上几个例题 ，后面做了再贴代码

最大连续和：hdu1003 模板题

#include <stdio.h>

int main()
{
	int T;
	int N,num;
	int ans,sum,flag,x,y;
	scanf("%d",&T);
	for(int cas = 1; cas <= T; cas ++)
	{
		scanf("%d",&N);
		ans = -1001;//这里的最小是-1000
		sum = 0;
		x = y = 1;
		flag = 1;
		for(int i = 1; i <= N; i ++)
		{
			scanf("%d",&num); //这里也可以在每个案例下 先输入N个数，这里 就sum += a[i];
			sum += num;
			if(sum > ans)
			{
				ans = sum;
				x = flag;
				y = i;
			}
			if(sum < 0)
			{
				sum = 0;
				flag = i+1;
			}
		}
		printf("Case %d:\n%d %d %d\n",cas,ans,x,y);
		if(cas != T) printf("\n");
	}
	return 0;
}

最大子矩阵和：poj1050=hdu1081

#include<stdio.h>
#include<string.h>

int N;
int map[101][101];
int temp[101];

void Input()
{
	for(int i = 1;i <= N;i ++)
		for(int j = 1;j <= N;j ++)
			scanf("%d",&map[i][j]);
}

int getsum()
{
	int sum = 0,max = 0;//不用初始为-127，可以一个数也不加
	for(int i = 1;i <= N;i ++)
	{
		sum += temp[i];
		if(sum > max) max = sum;
		if(sum < 0) sum = 0;
	}
	return max;
}

void dp()
{
	int ans = -127;
	for(int i = 1;i <= N;i ++)//从第i行开始
	{
		memset(temp,0,sizeof(temp));
		for(int j = i;j <= N;j ++)//从i行到j行都尝试一次
		{
			for(int k = 1;k <= N;k ++)//把i到j行的每一列加起来。。。就是矩阵压缩
				temp[k] += map[j][k];

			int pre = getsum();//计算压缩的最大和
			if(ans < pre)//注意范围-127.。
				ans = pre;
		}
	}
	printf("%d\n",ans);
}

int main()
{
	while(~scanf("%d",&N))//注意hdu1081是多案例
	{
	 Input();
	 dp();
	}
	return 0;
}

个人愚昧观点，欢迎指正与讨论