学步园

给定一个如下的二维数组a[][]

1   3   5   7   4

2   1   8   6   5

4   0  -1  -2   6

求其中的最长递减子序列：7, 5, 3, 1, 0, -1, -2，长度为7。子序列只能朝向上下左右四个方向，不能朝对角线方向。

思路：

该题一看感觉可以用动态规划做，但是下标不确定从哪里开始算起，因为有上下左右四个方向，没有办法顺序计算。只有用递归的方法来做。用一个函数FindMax(i, j)来表示以该位置起始的最长递减子序列的长度，那么只要取FindMax(i-1, j)、FindMax(i+1, j)、FindMax(i, j-1)、FindMax(i, j+1)中的最大值，然后加1即可，当然前提是上下左右的元素比(i, j)的元素小。

代码如下：

#include <iostream>
#include <assert.h>
using namespace std;

int Max(int a, int b, int c, int d)
{
	a = (a > b) ? a : b;
	a = (a > c) ? a : c;
	return (a > d) ? a : d;
}

int FindMax(int a[], int res[], bool flag[], int m, int n, int i, int j)
{
	int umax = 0, dmax = 0, lmax = 0, rmax = 0;
	//当前元素的下标
	int cur = i * n + j;

	//上面的元素
	int up = (i - 1) * n + j;
	//如果存在上面的元素，并且当前元素大于上面元素，就计算上面元素的最长路径
	if (i > 0 && a[cur] > a[up])
	{
		//如果上面元素的标记为false，说明上面元素的最长路径还没有计算
		if (!flag[up])
		{
			//计算上面元素的最长路径，计算结束后将上面元素的标记赋值为true
			umax = FindMax(a, res, flag, m, n, i-1, j);
			res[up] = umax;
			flag[up] = true;
		}
		//如果上面元素的标记为true，说明已经计算过，直接取结果
		else
			umax = res[up];
	}

	//下面的元素
	int down = (i + 1) * n + j;
	if (i < m-1 && a[cur] > a[down])
	{
		if (!flag[down])
		{
			dmax = FindMax(a, res, flag, m, n, i+1, j);
			res[down] = dmax;
			flag[down] = true;
		}
		else
			dmax = res[down];
	}

	//左边的元素
	int left = i * n + j - 1;
	if (j > 0 && a[cur] > a[left])
	{
		if (!flag[left])
		{
			lmax = FindMax(a, res, flag, m, n, i, j-1);
			res[left] = lmax;
			flag[left] = true;
		}
		else
			lmax = res[left];
	}

	//右边的元素
	int right = i * n + j + 1;
	if (j < n-1 && a[cur] > a[right])
	{
		if (!flag[right])
		{
			rmax = FindMax(a, res, flag, m, n, i, j+1);
			res[right] = rmax;
			flag[right] = true;
		}
		else
			rmax = res[right];
	}

	//当上下左右元素的值都计算完，就可以计算当前元素的最长路径了
	flag[cur] = true;
	res[cur] = 1 + Max(umax, dmax, lmax, rmax);
	return res[cur];
}

int LDS(int a[], int m, int n)
{
	assert(a != NULL && m > 0 && n > 0);
	int* res = new int[m * n];
	memset(res, 0, m*n*sizeof(int));
	bool* flag = new bool[m * n];
	memset(flag, false, m*n*sizeof(bool));
	int max = 0;
	//计算以每个元素起始的最长路径长度，并记录全局的最长路径长度max
	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int cur = i * n + j;
			if (!flag[cur])
				FindMax(a, res, flag, m, n, i, j);
			if (max < res[cur])
				max = res[cur];
		}
	}
	delete [] res;
	delete [] flag;
	return max;
}


void main()
{
	int a[] = {
		100,100,18,19,20,
		10,100,16,100,14,
		12,14,15,100,12,
		100,100,11,100,11,
		100,100,9,100,7};
	int m = 5, n = 5;
	cout << LDS(a, m, n) << endl;
}