文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 DP超時解
    • 2.2 DP解

1. 題目

有 k 種顏色的涂料和一個包含 n 個柵欄柱的柵欄，每個柵欄柱可以用其中一種顏色進行上色。

你需要給所有柵欄柱上色，并且保證其中相鄰的柵欄柱 最多連續(xù)兩個 顏色相同。然后，返回所有有效涂色的方案數。

注意:
n 和 k 均為非負的整數。

示例: 輸入: n = 3，k = 2 輸出: 6 解析: 用 c1 表示顏色 1，c2 表示顏色 2，所有可能的涂色方案有:柱 1 柱 2 柱 3 ----- ----- ----- ----- 1 c1 c1 c2 2 c1 c2 c1 3 c1 c2 c2 4 c2 c1 c1 5 c2 c1 c26 c2 c2 c1

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/paint-fence
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。

2. 解題

2.1 DP超時解

• 超時例子， 64 / 79 個通過測試用例

2 n 46340 k，時間復雜度O(nk^2) class Solution { public:int numWays(int n, int k) {if(n==0 || k==0)return 0;int conti = 2;//最多連續(xù)的次數vector<vector<vector<int>>> dp(n,vector<vector<int>>(k,vector<int>(conti+1,0)));//dp[i][c][conti]表示遍歷完i柵欄，其顏色為c，c顏色連續(xù)了conti次的方案數int i, c, nc, ct;for(c = 0; c < k; ++c)dp[0][c][1] = 1;for(i = 1; i < n; ++i){for(c = 0; c < k; ++c){for(ct = 1; ct <= conti; ++ct)for(nc = 0; nc < k; ++nc){if(c == nc && ct+1 <= conti)dp[i][nc][ct+1] += dp[i-1][c][ct];else if(c != nc)dp[i][nc][1] += dp[i-1][c][ct];}}}int sum = 0;for(c = 0; c < k; ++c)for(ct = 1; ct <= conti; ++ct)sum += dp[n-1][c][ct];return sum;} };

2.2 DP解

• 前兩個顏色一樣，dp[i-2] 的方案數，dp[i-2]*1*(k-1)，i 跟他們必須不一樣（k-1種選擇）
• 前兩個顏色不一樣，i-2 占了一種顏色， i-1 占了一種顏色，i 還能選擇 k-1 種顏色（可以跟 i-2 一樣），方案數為 dp[i-1]*(k-1)

class Solution { public:int numWays(int n, int k) {if(n==0 || k==0)return 0;vector<int> dp(n,0);//dp[i]表示遍歷完i柵欄的方案數if(n>=1)dp[0] = k;if(n>=2)dp[1] = k*k;for(int i = 2; i < n; ++i){dp[i] = dp[i-1]*(k-1)+dp[i-2]*(k-1);}return dp[n-1];} };

0 ms 6.2 MB

class Solution: # py3def numWays(self, n: int, k: int) -> int:if n==0 or k==0:return 0dp = [0]*nif n >= 1:dp[0] = kif n >= 2:dp[1] = k**2for i in range(2, n):dp[i] = (dp[i-1]+dp[i-2])*(k-1)return dp[n-1]

36 ms 13.6 MB

• 狀態(tài)可以進一步壓縮成3個變量，代碼略

---

長按或掃碼關注我的公眾號，一起加油、一起學習進步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 276. 栅栏涂色（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。