当前位置： 面试刷题>> 栅栏染色 (经典算法题500道)
### 题目描述补充
**题目：栅栏染色**
给定一个长度为 `n` 的栅栏，每个位置可以涂上红色、绿色或蓝色三种颜色之一。但是，相邻的栅栏位置不能涂相同的颜色。现在，要求你计算并返回所有可能的染色方案数。
**示例输入**：
- 栅栏长度 `n = 3`
**示例输出**：
- 可能的染色方案数 `= 6`
解释：对于长度为3的栅栏，可能的染色方案有：RGB, RBG, GRB, GBR, BRG, BGR（其中R代表红色，G代表绿色，B代表蓝色）。
### PHP 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课**：在算法和数据结构的学习中，理解动态规划的思想尤为重要。上述题目通过动态规划的方式，有效地解决了栅栏染色的计数问题。码小课网站中有更多关于动态规划、递归、贪心算法等经典算法问题的详细解析和代码实现，欢迎大家前往学习交流。