简单思路就是前半和后半都做个表 (其实可以用同一个表)

表的内容是 { 值 => 和为这个值的排列数 }, 然后复杂度就 √n 了

#1 楼 @luikore 你这个并不快吧，生成你所说的 table 是比较慢的。

#2 楼 @zuozuo

我写了个 https://gist.github.com/luikore/5850721 , 就是查表的，0.1 秒不到

#3 楼 @luikore 这个挺快的 谢谢：）

这个是个动态规划问题，先用动态规划预处理 i 个数字和为 j 的排列方案数 dp[i][j]. 递推方程为 dp[i][j] = sum { dp[i-1][j-k]} , (0 <= k <= 9} . 长度为 n 的 lucky number 方案总数 ans = sum { dp[half][s] * dp[n-half][s]} ，其中 half = n/2.

c++ 代码见：http://ideone.com/intocY

之前一直用 C++ 做 acm 题，所以就写 c++ 了。。

ruby 写算法，总觉得别扭。。