f(n,x)代表长度为n  的 左边n/2位的和 减去 右边n/2位的和 为 x 的方法数
首先有对称性： f(n,-x)==f(n,x)
接下来我们举例说明转移方程,比如六位数：

——  ——  ——   ——   ——   —— 要求左右和差为 x

我们把它分开来看成：

——  ——           ——   ——          四位数，假设左右和之差为a

                 ——                     —— 两位数，。。。。。。。为b

那么a+b==x 的话即使我们要求的六位数

下面由乘法原理即可得到，并且注意到 a，b 的范围是与长度有关的，所以
只累加符合范围之内的 如   -9<=b<=9

函数如下：


int f(int n,int x)
{
	if(dp[n][x]!=-1)return dp[n][x];//记忆化
	if(n==2)
	{
		int sum=0;
		for(int a=0;a<=9;a++)
			for(int b=0;b<=9;b++)
				if(a-b==x)sum++;
		return dp[n][x]=sum;
	}
	int a,b,sum=0;
	for(b=-9;b<=9;b++)
	{
		a=x-b;
		if(a>=-9*(n-2)/2&&a<=9*(n-2)/2)
			sum+=f(n-2,abs(a))*f(2,abs(b));
	}
	return dp[n][x]=sum;
}

其实，个人建议很多dp题都可以用递归函数+状态记忆写出，既方便又好理解，
行云流水，而本质上来说，dp其实就是记忆化的搜索，搜索还是核心吧

• Re:非常简单思路 记忆化搜索 （dp） 供大家学习 (0) 604567212 2011-07-13 13:55:38
• Re:南理工的，果断顶啊！ (0) 604567212 2011-07-13 13:56:08