给定一个仅由 4 个不同字母组成的字符串，在没有两个连续字母的情况下存在多少种排列？
Given a string formed only with 4 different letters, how many permutations of it exist with no two consecutive letters?
给定一个字符串 S，由字母 A、B、C、D 组成，每个字母最多出现 10 次 S
S有多少个排列不包含2个连续字母？
例如给定
A: 3 times, B: 1 time, C: 1, D: 0
ABACA is valid
AABAC is invalid
我试过包含排除，但我的模型无法产生一组好的属性来使用该原理。
有公式还是我漏了什么？
是动态规划
从头开始创建每个排列，因此您在字符串末尾一次添加一个字母
假设你刚刚使用了字母'A'，下一个字母不可能是'A'，你比之前少了1个字母'A'，所以你继续这个过程直到你运行 出字母
让
f(prohibited, A, B, C, D)
大小为A + B + C + D的字符串数量A个字母'A', B 字母 'B', ... 并且此字符串不能以 prohibited
开头
假设禁止等于'A'，那么您有3个选项可供选择：
以字母 'B' 开头，然后，下一次，禁止的是 'B' 并且您有 B - 1 个字母 'B'，即是
f('B', A, B - 1, C, D)
如果您选择了 'C' 而不是 'B'，则禁止的是 'C' 并且您有 C - 1 个字母追加
求和也是如此
f('A', A - 1, B, C, D) + f('B', A, B - 1, C, D) ...
应该就可以了。
给定一个字符串 S，由字母 A、B、C、D 组成，每个字母最多出现 10 次 S S有多少个排列不包含2个连续字母？
例如给定
A: 3 times, B: 1 time, C: 1, D: 0
ABACA is valid
AABAC is invalid
我试过包含排除，但我的模型无法产生一组好的属性来使用该原理。
有公式还是我漏了什么？
是动态规划
从头开始创建每个排列，因此您在字符串末尾一次添加一个字母 假设你刚刚使用了字母'A'，下一个字母不可能是'A'，你比之前少了1个字母'A'，所以你继续这个过程直到你运行 出字母
让
f(prohibited, A, B, C, D)
大小为A + B + C + D的字符串数量A个字母'A', B 字母 'B', ... 并且此字符串不能以 prohibited
开头假设禁止等于'A'，那么您有3个选项可供选择：
以字母 'B' 开头，然后，下一次，禁止的是 'B' 并且您有 B - 1 个字母 'B'，即是
f('B', A, B - 1, C, D)
如果您选择了 'C' 而不是 'B'，则禁止的是 'C' 并且您有 C - 1 个字母追加
求和也是如此
f('A', A - 1, B, C, D) + f('B', A, B - 1, C, D) ...
应该就可以了。