用1，2，3三个数来构造六位数，但是不允许有两个连着的1出现在六位数中(例如322132，212122是允许的，113233，211122就是不允许的)，问这样的六位数一共有多少个用组合排列的方式求解

要解决这个问题，我们可以采用动态规划（Dynamic Programming，DP）的方法，通过构造状态转移方程来求解。考虑到不允许有两个连续的“1”出现，可以分阶段计算包含不同个数“1”的有效数字数量。 这里的状态定义为：`dp[i][j]` 表示长度为 `i` 的数字中包含 `j` 个“1”的合法数字数量。 #### 步骤： 1. **基础情况**：`dp[1][0] = 1`、`dp[1][1] = 1`，因为在一位数下，0个“1”是"3"或"2"，1个“1”是"1"。 2. **状态转移方程**： - 如果最后一位（第 `i` 位）是“2”，则第 `i-1` 位可以是 “1”、“2” 或 “3”，因此有 `3 * dp[i-1][j]`。 - 如果最后一位（第 `i` 位）是“3”，则第 `i-1` 位同样可以是 “1”、“2” 或 “3”，同样有 `3 * dp[i-1][j]`。 对于会出现两个连续“1”的情况： - 如果最后一位是“1”，我们需要考虑是否与其紧邻的“1”相连以决定能跳过选项。由于我们不允许两个连续“1”出现，因此： - 如果其前一位也是“1”（因为我们正在形成两位数），那么这个操作在长度i=1时已经控制过，所以在这里只需要考虑前面是多个“1”加上不是“1”的数字。因此，与上一位无关，最终任何非“1”都可以追加。 3. **组合阶段**： - 对于每一个长度 `i`，我们想要计数的是由几个“1”组成的数。状态转移方程组合数应考虑所有合法添加（即不增加两个连续的1）。 #### 具体编码 ```python def count_legal_numbers(): # 创建dp表 dp = [[0] * (7) for _ in range(7)] # 取长度到6是因为长度从1开始计算 # 基础情况 dp[1][0], dp[1][1] = 1, 1 # 填充dp表 for i in range(2, 7): # 实际只填充到6位 for j in range(7): # 需要记录最多6个1的情况 if j == 0: # 没有1的情况 dp[i][j] = 2 * dp[i - 1][j] + dp[i - 1][j + 1] # 仅2和3可以添加 elif j == 1: # 有一个1 dp[i][j] = dp[i - 1][j] + 2 * dp[i - 1][j - 1] # 已有1，再添加2或3 else: # 有多于1个1 dp