学步园

http://haixiaoyang.wordpress.com/category/dynamic-programming/

这个比求最大矩阵要方便多了，记录的是rec[i][j]矩阵边上的点的数目

//There is a square of n x n size which is comprised of n-square 1x1 squares. 
//Some of these 1x1 squares are colored. Find the biggest 
//sub square which is colored.  Also asked to extend it to find the biggest area rectangle

const int N = 5;
int FindLargestArea(bool A[N][N])
{
	int rec[N][N];
	int nRet = 0;
	for (int i = 0; i < N; i++)
	{
		rec[0][i] = A[0][i] ? 1 : 0;
		if (rec[0][i] > nRet)
			nRet = rec[0][i];
	}

	for (int i = 0; i < N; i++)
	{
		rec[i][0] = A[i][0] ? 1 : 0;
		if (rec[i][0] > nRet)
			nRet = rec[i][0];
	}

	for (int i = 1; i < N; i++)
	{
		for (int j = 1; j < N; j++)
		{
			if (!A[i][j])
			{
				rec[i][j] = 0;
				continue;
			}
			
			rec[i][j] = 1 + min(min(rec[i][j-1], rec[i-1][j]), rec[i-1][j-1]);

			//this is the first logic I write
			/*if (rec[i][j-1] == 0 || rec[i-1][j] == 0)
				rec[i][j] = 1;
			else
			{
				int nTmp = min(rec[i][j-1], rec[i-1][j]);

				//well, I missed the brackets leading to errors
				rec[i][j] = nTmp + (A[i-nTmp][j-nTmp] ? 1 : 0);
			}*/

			if (rec[i][j] > nRet)
				nRet = rec[i][j];
		}
	}

	return nRet;
}