令$f(n,i,j,d)$为n位、含有数字i到j (包括i和j)、且以数字d结尾的数，其中$i\le d\le j$。
显然
$$f(n, d, d, d)=\begin{cases}1 & d>0 \\ 0 & d=0\end{cases}$$
(必须排除$d=0$，否则无法正确排除带有前导0的表示，这是容易忽视和出错的部分)
f的其它值可以递推计算
$$f(n, i, j, d)=\begin{cases}f(n-1, i, j, d-1)+f(n-1, i, j, d+1) & i< d < j \\ f(n-1, i, j, d+1)+f(n-1, i+1, j, d+1) & d=i \\ f(n-1, i, j, d-1)+f(n-1, i, j-1, d-1) & d=j\end{cases}$$
这是因为若d在i和j之间，则其前一位可以是$d-1$或$d+1$。
若$d=i$，则根据i和j的定义其前一位只能是$d+1$，从而可能是由$f(n-1, i+1, j, d+1)$转移而得（表示前n-1位都不含d），也可能是由$f(n-1, i, j, d+1)$转移而得（表示d已经出现过）。
$d=j$的情况也类似。
结果是$126461847755$。
f=[[[[1 if i==j==k>0 else 0 for k in range(10)] for j in range(10)] for i in range(10)] for n in range(41)]
for n in range(2,41):
for i in range(10):
for j in range(i,10):
for d in range(i,j+1):
if i < d and d < j:
f[n][i][j][d]=f[n-1][i][j][d-1]+f[n-1][i][j][d+1]
elif i==d and d < 9:
f[n][i][j][d]=f[n-1][i][j][d+1]+f[n-1][i+1][j][d+1]
elif d>0:
f[n][i][j][d]=f[n-1][i][j][d-1]+f[n-1][i][j-1][d-1]
print sum(sum(f[n][0][9][d] for d in range(10)) for n in range(1,41))
|
