九小时九个人九扇门

对于每个人来说，他们都有一个数，并且这些数的范围是 [0 , 9] 我们很容易的想到使用DP的思路来解决问题。

我们设 f[n , m] 表示前 n 个人一共可以组合出来多少个结果为 m 的个数。 那么我们便可以得到这样的转移式子对于第 i 个人来说，其本身就是一种情况，因此 f[i , v[i]] ++ 是必要的。那么对于前一个位的 10 种情况而言假设原根为 g(x) ,那么状态转移方程如下所示

转化为代码

for (int i = 1 ; i <= n ; i ++) {
  f[i][v[i]] = 1;
  for (int j = 0 ; j <= 9 ; j ++) {
    f[i][g(v[i] + j)] += f[i - 1][j];
  }
}

code