algorithm - 计算总组合

Question

我不知道如何解决这个编程问题。

给定两个整数 n 和 m，存在多少个数字使得所有数字的所有数字都从 0 到 n-1，并且两个相邻数字之间的差正好为 1，并且该数字中的数字个数最多为 'm' .

解决这个问题的最佳方法是什么？有直接的数学公式吗？

编辑:数字不能以 0 开头。

例子: 对于 n = 3 和 m = 6，有 18 个这样的数字(210、2101、21012、210121 ... 等)

更新(有些人遇到过歧义): 所有 数字从 0 到 n-1 必须存在。

Answer 1

此 Python 代码通过跟踪以特定数字结尾的数字以 O(nm) 计算答案。

不同的数组(A、B、C、D)用于跟踪达到范围最大值或最小值的数字。

n=3
m=6
A=[1]*n # Number of ways of being at digit i and never being to min or max
B=[0]*n # number of ways with minimum being observed
C=[0]*n # number of ways with maximum being observed
D=[0]*n # number of ways with both being observed
A[0]=0 # Cannot start with 0
A[n-1]=0 # Have seen max so this 1 moves from A to C
C[n-1]=1 # Have seen max if start with highest digit
t=0
for k in range(m-1):
    A2=[0]*n
    B2=[0]*n
    C2=[0]*n
    D2=[0]*n
    for i in range(1,n-1):
        A2[i]=A[i+1]+A[i-1]
        B2[i]=B[i+1]+B[i-1]
        C2[i]=C[i+1]+C[i-1]
        D2[i]=D[i+1]+D[i-1]
    B2[0]=A[1]+B[1]
    C2[n-1]=A[n-2]+C[n-2]
    D2[0]=C[1]+D[1]
    D2[n-1]=B[n-2]+D[n-2]
    A=A2
    B=B2
    C=C2
    D=D2
    x=sum(d for d in D2)
    t+=x
print t