题目要求n位数字前 (n/2) 位各位数字之和与后 (n/2) 位各位数字之和相等的数字的个数。
那就可以先求出 (n/2) 位的所有数字中，各位数字之和为 0、1、2、……、(n/2)*9 的数字的个数，再求出这些个数的平方和就可以了。

假设用 num(i,j) 表示一共i位数字，各位数字之和为j的数字的个数
显然有：
num(1,0..9) = 1
num(x,0) = 1   (x > 0)
下面讨论 num(i,j) 的一般情况：
首先约定用 D(i,j) 表示所有一共 i 位数字，各位和为 j 的数字所组成的集合。
(1).
由于 D(i-1,j) 里面的数字都是 (i-1) 位，和为 j ，那么可以对 D(i-1,j) 里面的每一个数字前面加个 0 作为首位，就可以得到 D(i,j) 中首位数字是0的所有数字。
(2).
由于 D(i,j-1) 里面的数字都是 i 位，和为 (j-1)，那么可以对 D(i,j-1 )里面的每一个数字加个 1，就可以得到 D(i,j) 中的一些数字。
在(1)中求得了 D(i,j) 中首位数字是 0 的所有数字，但是，
D(i,j-1) 中也含有首位数字是 0 的数字，怎么办？
只好把 1 也加到 D(i,j-1) 中所有首位数字是 0 的数字的首位上。也就是把首位的 0 变成 1。
可这样又产生了同样的问题：
D(i,j-1) 中也含有首位数字是 1 的数字，怎么办？
只好把 1 也加到 D(i,j-1) 中所有首位数字是 1 的数字的首位上。也就是把首位的 1 变成 2。
以此类推，只要把 D(i,j-1) 中的每一个数字的首位都加上 1 即可。
至此，得到方程：num(i,j) = num(i-1,j) + num(i,j-1)
(3).
此时又出现了新的问题：
当 j-1>=9 时，原来 D(i,j-1) 中所有首位数字是 9 的数字怎么办？加了 1 就会进位，导致多了1位。
在(2)中，D(i,j-1) 中首位为 1-8 的数字进行了改造，得到了 D(i,j) 中首位数字是 1-9 的数字。
显然 D(i,j-1) 中首位数字是 9 的数字是多余的，要将其排除掉。
那么它的个数有多少呢？
将这些数字的首位数字 9 去掉，那么剩下 (i-1) 位，其和为 (j-1-9) = (j-10)。
也就是说， D(i,j-1) 中首位数字是 9 的数字的个数有 num(i-1,j-10)个。

综合以上3条，得到最终方程：
num(i,j) = num(i-1,j) + num(i,j-1)                    (j < 10)
num(i,j) = num(i-1,j) + num(i,j-1) - num(i-1,j-10)    (j >= 10)

• 顶一个 (1) scaneeling 2008-09-26 19:44:11
• Re:此题DP做法 (1781) dreamone 2008-10-06 23:36:54
• Re:此题DP做法 (45) Staryin 2008-10-19 10:31:49
  • Re:此题DP做法 (62) gaoxiaomeng 2009-08-19 11:25:20
  • Re:此题DP做法 (311) tzkq 2010-06-10 03:21:10
• Re:此题DP做法 (16) xujiaming 2008-10-28 08:23:11
• 分析得很细！ (283) qrmajia 2009-02-24 22:01:11
  • 顶！！！ (5) zhouxiaozi 2009-03-05 13:34:04
• Re:此题DP做法 (21) anchong 2010-01-30 20:20:15
• 顶一个 (0) anchong 2010-01-30 20:20:59
• 看起来好复杂哦，还不如用n/2*n*9*9的算法。。。 (0) swust20105592 2011-10-29 19:03:36
• 谢谢好思路 (0) DEQDON 2012-10-29 18:00:22
• 大赞~ (0) HeadHunter 2013-04-05 23:51:35
• 是我没看懂？还是怎么回事。。？ (400) Muye007 2013-10-15 01:58:05