题目描述补充

题目：栅栏染色

给定一个长度为 n 的栅栏，每个位置可以涂上红色、绿色或蓝色三种颜色之一。但是，相邻的栅栏位置不能涂相同的颜色。现在，要求你计算并返回所有可能的染色方案数。

示例输入：

• 栅栏长度 n = 3

示例输出：

• 可能的染色方案数 = 6

解释：对于长度为3的栅栏，可能的染色方案有：RGB, RBG, GRB, GBR, BRG, BGR（其中R代表红色，G代表绿色，B代表蓝色）。

PHP 示例代码

function countColoringWays($n) {
    if ($n == 0) return 0;
    if ($n == 1) return 3;

    // dp[i] 表示长度为 i 的栅栏的染色方案数
    $dp = array_fill(0, $n + 1, 0);
    $dp[1] = 3;
    $dp[2] = 6; // RGB, RBG, GRB, GBR, BRG, BGR

    for ($i = 3; $i <= $n; $i++) {
        // 对于第 i 个栅栏，它不能和前一个颜色相同，所以考虑前两个栅栏的颜色
        // 假设前两个栅栏的颜色组合为 AB，则第 i 个栅栏可以是 C（C ≠ B）
        // 因此，dp[i] = dp[i-1] * 2（因为对于每种 i-1 的方案，第 i 个栅栏都有两种选择）
        // 但要注意，当 i=3 时，AB 和 BA 是两种不同的方案，所以 dp[3] = 2 * dp[2]
        // 但从 i=4 开始，ABXXX 和 BAXXX 实际上是同一种方案（因为 XXX 可以是任意合法染色），
        // 所以只需考虑 dp[i-1] 的情况，并乘以 2（除了和前一个颜色相同的颜色外，还有两种选择）
        $dp[$i] = $dp[$i - 1] * 2;
    }

    return $dp[$n];
}

echo countColoringWays(3); // 输出 6

Python 示例代码

def countColoringWays(n):
    if n == 0:
        return 0
    if n == 1:
        return 3

    dp = [0] * (n + 1)
    dp[1] = 3
    dp[2] = 6

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] * 2

    return dp[n]

print(countColoringWays(3))  # 输出 6

JavaScript 示例代码

function countColoringWays(n) {
    if (n === 0) return 0;
    if (n === 1) return 3;

    let dp = new Array(n + 1).fill(0);
    dp[1] = 3;
    dp[2] = 6;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] * 2;
    }

    return dp[n];
}

console.log(countColoringWays(3)); // 输出 6

码小课：在算法和数据结构的学习中，理解动态规划的思想尤为重要。上述题目通过动态规划的方式，有效地解决了栅栏染色的计数问题。码小课网站中有更多关于动态规划、递归、贪心算法等经典算法问题的详细解析和代码实现，欢迎大家前往学习交流。