摘要

在用戶體驗和界面設計中，顏色搭配是個繞不開的核心問題。而在 LeetCode 的一道經典題目「柵欄涂色」中，系統地將這個看似簡單的“上色”問題轉化為一道有趣的動態規劃挑戰。今天我們就用 Swift 帶你一探這個問題背后的“涂色學”，并分析它的數學規律、代碼實現以及實際意義。

描述

題目大意很簡單：你要給一排 n 根柵欄涂色。你一共有 k 種顏色可以選擇，但有一個限制條件：不能有超過兩根相鄰的柵欄使用同一種顏色。

你需要返回總共有多少種不同的涂色方法。

例子：

輸入: n = 3, k = 2
輸出: 6
解釋:
可能的涂色方式如下：
1. 紅 紅 藍
2. 紅 藍 紅
3. 紅 藍 藍
4. 藍 藍 紅
5. 藍 紅 藍
6. 藍 紅 紅

題解答案（Swift）

這個題目是動態規劃的典型題，我們需要考慮狀態轉移和子問題的劃分。簡單來說，我們要區分兩種情況：

• same: 最后兩根柵欄顏色相同
• diff: 最后兩根柵欄顏色不同

根據這兩個狀態，我們可以構造出一個高效的遞推公式。

func numWays(_ n: Int, _ k: Int) -> Int {if n == 0 { return 0 }if n == 1 { return k }var same = 0var diff = kvar total = same + difffor _ in 2...n {same = diffdiff = total * (k - 1)total = same + diff}return total
}

題解代碼分析

動態規劃核心思路

我們用 same 表示前兩根柵欄顏色相同的方案數，diff 表示前兩根顏色不同的方案數。總方案數就是這兩者之和。

遞推關系如下：

• 當前的 same = diff（因為如果前一輪是不同色的，當前這一輪就可以延續相同顏色）
• 當前的 diff = total * (k - 1)（從上一個狀態的所有組合中選擇不同的顏色）

我們每輪都更新這兩個變量，直到涂完 n 根柵欄。

初始條件

• 當 n = 1，只有 k 種可能。

• 當 n = 2，我們可以有：

  • 相同顏色：k（比如紅紅、藍藍）
  • 不同顏色：k * (k - 1)（比如紅藍、藍紅）

示例測試及結果

示例 1：

let result = numWays(3, 2)
print(result)  // 輸出: 6

這個結果就跟題目中的例子一致，一共 6 種組合。

示例 2：

let result = numWays(1, 3)
print(result)  // 輸出: 3

只有一根柵欄，那就直接從三種顏色里選一種。

示例 3：

let result = numWays(4, 3)
print(result)  // 輸出: 66

解釋較復雜，但動態規劃會自動幫你計算出來所有組合。

時間復雜度

• O(n)
  我們遍歷一遍從 2 到 n，所以時間復雜度是線性的。

空間復雜度

• O(1)
  我們只用了幾個變量，沒有額外數組存儲，空間復雜度為常數級。

總結

這個問題雖然看起來像是簡單的排列組合，但真正下手的時候會發現，不加限制的排列很容易，但加了“不能超過兩個相同顏色”的規則后就變得有點挑戰性了。

動態規劃的好處就是可以把問題拆成更小的部分，一步步向目標推進。在這題中，理解 same 和 diff 這兩個狀態是關鍵。

實際場景聯系

想象你是個裝修師傅，客戶讓你刷墻，說每面墻可以選擇多種顏色，但不希望連續三面墻刷成一樣的顏色（太單調了）。你要怎么安排？其實就是這道題！

或者你是個前端開發者，在設計界面時，需要生成用戶界面卡片顏色的方案，同樣不能讓相鄰部分顏色一致。解決方法也就是應用這種動態遞推模型。