学步园

原题网址：题目网址Topcoder

作为初步理解动态规划的自己照葫芦画瓢实现的小程序，还是比较有体会的，上次只是对问题进行了分析，对算法进行了设计。

实际上，对于算法的分析是有一点错误的。这里再次分析一下：

对于数据{1 17 5 10 13 15 10 5 16 8}

d[1] = 1,f[1] = +;

d[2] = {  v[1]-v[2]<0   },f[2] = -;

d[3] = {  v[1]-v[3]<0,因为是第一个与其相减，没有正负特性，所以可以采纳;

v[2]-v[3]>0, 正数，记录的f[2]是负数，相反，所以采纳 ；

max{d[1]+1,  d[2]+1},   所以采纳d[2]+1 }  f[3] = +;

d[4] = { v[1] - v[4] < 0 ,采纳;

v[2] - v[4] > 0 ,正数，记录f[2]负数，相反，采纳；

v[3] - v[4] <0 , 负数，记录f[3]的正数，相反，采纳；

max{ d[1]+1 , d[2]+1, d[3]+1 }  所以采纳d[3]+1}  f[4]= -;

d[5] = { v[1] - v[5] < 0 采纳；

v[2] - v[5] > 0 , 相反，采纳；

v[3] - v[5] <0 , 相反，采纳；

v[4] - v[5] <0 ,负数，记录f[4]负数，相同，不采纳；

max{ d[1]+1 , d[2]+1, d[3]+1 }  所以采纳d[3]+1；

这里和d[4]是一样的了，}  f[5] = - ;

…………

其中，d[i]表示前i个数中最大子序列；

v[i]表述输入字符串第i个字符；

f[i]表示前i个最大子序列中最后两个数字的差的正负性。

由此可以得出最终的实现代码：

	/*
6
1 7 4 9 2 5
10
1 17 5 10 13 15 10 5 16 8
	*/

#include <stdio.h>
#define M 500
int max(int x,int y)
{
	return x>y ? x:y;	
}

//judge the two number's p&n
int iscontrast(int a,int b)
{
	if( a > 0 && b < 0 || a<0 && b>0)
	{
		return 1;	
	}
	return 0;
}

int main()
{
	int d[M];
	int v[M];
	int f[M];//1 for positive ,-1 for negtive
	int i;
	int n;
	scanf("%d",&n);
	for(i=0 ; i<n ; i++)
	{
		scanf("%d",&v[i]);	
	}
	for(i=0 ; i< n; i++)
	{
		d[i] =  0;	
	}
	int j;
	d[0]=1;

	for(i=1 ; i < n ; i++)
	{
		for(j=0 ; j< i ; j++)
		{
			//if the condition is ok
			if( j==0 || iscontrast(f[j],v[j]-v[i])==1 )
			{
				d[i] = max(d[i],d[j]+1);
				//set the p&n of the current position 
				f[i] = v[j]-v[i] > 0 ? 1:-1;
			}	
		}	
	}
	printf("%d",d[n-1]);
	getchar();
	getchar();
	return 0;	
}

动归问题的核心就是建立起当前状态与前一个状态的状态转移方程，并根据具体情况存储必要的条件。

本题中关键的条件就是f[i] 前i个数字中最后两个数字差的正负性的存储以及设定。

同时动归的两重循环里面，各自的起始终止下标i,j  以及  初始化状态也需要比较好的确定。

以上就是初级动归问题实现之后的感觉。

希望之后又更深入的了解吧。