题目164：任意三个相邻数字位之和不超过给定值的数字

欧拉计划

Numbers for which no three consecutive digits have a sum greater than a given value

How many 20 digit numbers n (without any leading zero) exist such that no three consecutive digits of n have a sum greater than 9?

题目：

请问，存在多少个位数为 20（没有前导 0），并且任意三个相邻数位之和不超过 9 的数字？

jerryxjr1220

用广度优先搜索或者A*搜索可以解，问题是要求20位的话，花的时间会非常长。
我算了一下10位的，大概10秒多一点。每多一位要差不多5倍的时间。
这样算20位的话至少需要97656250秒，也就是计算机要跑3年。。。
我的天啊，应该能找到更好的方法来求解吧。

from collections import deque
def euler164(length=20):
        count = 0
        quee = deque(['1','2','3','4','5','6','7','8','9'])
        while quee:
                q = quee.popleft()
                tt = 0
                for i in range(min(len(q),2)):
                        tt += int(q[-1-i])
                if tt > 9: continue
                for j in range(10-tt):
                        if len(q)+1 == length:
                                count += 1
                                #print(q+str(j), count)
                                continue
                        else:
                                quee.appendleft(q+str(j))
        return count
print(euler164(10))
# 3                165
# 4                990
# 5                5445
# 6                27588
# 7                146586
# 8                783057
# 9                4129851
# 10                21838806

guosl

答案：378158756814587
应用递推即可。

#include <iostream>
using namespace std;

long long f[21][10][10];

int main(void)
{
  for (int i = 1; i <= 9; ++i) //枚举首位数
    f[1][i][0] = 1;
  for (int n = 2; n <= 20; ++n) //数字的位数
  {
    for (int m1 = 0; m1 <= 9; ++m1) //枚举最后一位
    {
      for (int m2 = 0; m2 <= 9; ++m2)//枚举最后二位
      {
        int k = m1 + m2;
        if (k > 9)
          break;
        for (int m3 = 0; m3 <= 9 - k; ++m3)////枚举最后三位
          f[n][m1][m2] += f[n - 1][m2][m3];
      }
    }
  }
  long long nCount = 0;
  for (int m1 = 0; m1 <= 9; ++m1) //求和
  {
    for (int m2 = 0; m2 <= 9; ++m2)
      nCount += f[20][m1][m2];
  }
  cout << nCount << endl;
  return 0;
}

瓦屋青衣

import time
import math

timeStart = time.time()

n = 20

dic = {}
lis = [(i ,j) for i in range(10) for j in range(10) if i+j <= 9]
for tp in lis:
    dic[(3, *tp)] = 9-sum(tp)
for x in range(4, 1+20):
    for tp in lis:
        for y in range(10-sum(tp)):
            dic[(x, *tp)] = dic.setdefault((x, *tp), 0) + dic[(x-1, y, tp[0])]
#[print(k, v) for k, v in dic.items()]

ans = sum(dic[(n, *tp)] for tp in lis)

print(ans)

print(f'time used: {time.time() - timeStart: .3f} s')