$k$个字母的长为$n$单词个数, 不含连续 $m$ 个A

hbghlyj

相关
Given positive integers $k,m,n$ and a $k$-ary alphabet (containing $A$), compute the number of strings of length $n$ that have no substring of $m$ consecutive $A$s.

oi-wiki.org/dp/

hbghlyj

设 $f_{i,j}$ 是长度为 $i$ 的 $k$ 元字符串的数量，这些字符串以 $j$个连续 $A$ 结尾并且不包含 $m$ 个连续$A$。
We can compute $f_{i,j}$ recursively as follows:
Last letter is $m$: $f_{i,j} = f_{i-1,j-1}$, for $0<j<m$.
Last letter is not $m$: $f_{i,0} =(k-1)\sum_{j=0}^{\min(i,m)-1}f_{i-1,j}$
The base cases are $f_{i,i} = 1$ for $i<m$ and $f_{i,j} = 0$ for $j\geq m$.

To compute the answer, we can use the following Mathematica code:

1. ForbiddenSubstring[k_, m_, n_] := Block[{f}, f[i_, i_] := 1;
2.   f[i_, m] := 0;
3.   f[i_, 0] := (k - 1) Sum[f[i - 1, j], {j, 0, Min[i, m] - 1}];
4.   f[i_, j_] := If[j < m, f[i - 1, j - 1], 0];
5.   Sum[f[n, j], {j, 0, Min[n, m - 1]}]]

Copy the Code

Example
ForbiddenSubstring[2, 3, 5]输出24
枚举Length[Select[StringJoin /@ Tuples[{"A", "B"}, 5], StringFreeQ["AAA"]]]也输出24

hbghlyj

Timing[ForbiddenSubstring[5, 5, 15]]输出运行时间为0.0625秒
使用Memoization (记忆化搜索)将代码优化为

1. ForbiddenSubstring[k_, m_, n_] := Block[{f}, f[i_, i_] := 1;
2.   f[i_, m] := 0;
3.   f[i_, 0] := (f[i, 0] = (k - 1) Sum[f[i - 1, j], {j, 0, Min[i, m] - 1}]);
4.   f[i_, j_] := (f[i, j] = If[j < m, f[i - 1, j - 1], 0]);
5.   Sum[f[n, j], {j, 0, Min[n, m - 1]}]]

Copy the Code

Timing[ForbiddenSubstring[5, 5, 15]]输出运行时间为0.秒