用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）。

具体编码

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