LeetCode 粉刷栅栏Paint Fence动态规划全解从递归记忆化到 O(1) 空间优化【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南围绕 LeetCode 经典题Paint Fence粉刷栅栏展开完整讲解其动态规划解法自顶向下递归 记忆化、自底向上填表、以及常数空间滚动优化三种实现路径并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 等多语言可运行代码。阅读完本文你将理解「最多连续两根柱子同色」约束下的状态转移推导过程掌握totalWays(i) (k - 1) * (totalWays(i - 1) totalWays(i - 2))递推公式的由来并能针对任意n个栅栏柱与k种颜色在 O(n) 时间内求出合法涂色方案总数。问题背景与约束理解题目给定n个栅栏柱和k种颜色要求为每根柱子涂色并且不能出现连续三根及以上柱子使用相同颜色。也就是说至多允许两根相邻柱子同色。要求返回所有合法涂色方案的数量。本仓库以 articles/paint-fence.md 为入口收录了该题的完整题解仓库根目录的 README.md 按题号组织全部题解索引。理解题目约束是正确推导递推式的第一步详见后文「常见陷阱」一节。前置知识在动手编码前建议先熟悉以下动态规划基础概念本仓库的 articles/climbing-stairs.md 与 articles/house-robber.md 是很好的入门对照材料动态规划基础Dynamic Programming Fundamentals理解重叠子问题overlapping subproblems与最优子结构optimal substructure两大特征递推关系Recurrence Relations能够推导并实现「当前状态由前序状态决定」的公式记忆化Memoization缓存递归结果避免重复计算空间优化Space Optimization当 DP 表只依赖前几个状态时将其压缩为常数空间。解法一自顶向下动态规划递归 记忆化思路推导核心约束是「最多连续两根柱子同色」。因此对第i根柱子只有两种决策涂一种与第i - 1根不同的颜色此时无论前两根什么颜色都合法共有k - 1种选法对应(k - 1) * totalWays(i - 1)涂一种与第i - 1根相同的颜色此时必须保证第i - 1根与第i - 2根颜色不同否则会出现三连这一部分恰好对应totalWays(i - 2)中「第 i-1 与 i-2 不同」的方案数而「与第 i-1 相同」只有 1 种选法因此贡献为1 * totalWays(i - 2)。两种情况相加即得递推式totalWays(i) (k - 1) * (totalWays(i - 1) totalWays(i - 2))这里需要特别说明第二项的直觉totalWays(i - 2)已经涵盖所有合法的前i - 2根柱子涂法在其中任意一种方案上让第i - 1与第i - 2不同色、第i与第i - 1同色都不会产生三连同色故可直接复用。算法步骤定义totalWays(i)返回给柱子1到i合法涂色的方案总数边界条件totalWays(1) ktotalWays(2) k * k两根柱子任意组合不存在三连问题对i 2套用递推式totalWays(i) (k - 1) * (totalWays(i - 1) totalWays(i - 2))用哈希表字典记忆化缓存已计算结果避免重复递归返回totalWays(n)。多语言实现Pythonclass Solution: def numWays(self, n: int, k: int) - int: def total_ways(i): if i 1: return k if i 2: return k * k # Check if we have already calculated totalWays(i) if i in memo: return memo[i] # Use the recurrence relation to calculate total_ways(i) memo[i] (k - 1) * (total_ways(i - 1) total_ways(i - 2)) return memo[i] memo {} return total_ways(n)Javaclass Solution { private HashMapInteger, Integer memo new HashMapInteger, Integer(); private int totalWays(int i, int k) { if (i 1) return k; if (i 2) return k * k; // Check if we have already calculated totalWays(i) if (memo.containsKey(i)) { return memo.get(i); } // Use the recurrence relation to calculate totalWays(i) memo.put(i, (k - 1) * (totalWays(i - 1, k) totalWays(i - 2, k))); return memo.get(i); } public int numWays(int n, int k) { return totalWays(n, k); } }Cclass Solution { private: unordered_mapint, int memo; int totalWays(int i, int k) { if (i 1) return k; if (i 2) return k * k; // Check if we have already calculated totalWays(i) if (memo.find(i) ! memo.end()) { return memo[i]; } // Use the recurrence relation to calculate totalWays(i) memo[i] (k - 1) * (totalWays(i - 1, k) totalWays(i - 2, k)); return memo[i]; } public: int numWays(int n, int k) { return totalWays(n, k); } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number} */ numWays(n, k) { const memo {}; const total_ways (i) { if (i 1) { return k; } if (i 2) { return k * k; } // Check if we have already calculated total_ways(i) if (i in memo) { return memo[i]; } // Use the recurrence relation to calculate total_ways(i) memo[i] (k - 1) * (total_ways(i - 1) total_ways(i - 2)); return memo[i]; }; return total_ways(n); } }C#public class Solution { private Dictionaryint, int memo new Dictionaryint, int(); private int TotalWays(int i, int k) { if (i 1) return k; if (i 2) return k * k; if (memo.ContainsKey(i)) { return memo[i]; } memo[i] (k - 1) * (TotalWays(i - 1, k) TotalWays(i - 2, k)); return memo[i]; } public int NumWays(int n, int k) { return TotalWays(n, k); } }Gofunc numWays(n int, k int) int { memo : make(map[int]int) var totalWays func(i int) int totalWays func(i int) int { if i 1 { return k } if i 2 { return k * k } if val, ok : memo[i]; ok { return val } memo[i] (k - 1) * (totalWays(i-1) totalWays(i-2)) return memo[i] } return totalWays(n) }Kotlinclass Solution { fun numWays(n: Int, k: Int): Int { val memo HashMapInt, Int() fun totalWays(i: Int): Int { if (i 1) return k if (i 2) return k * k if (i in memo) return memo[i]!! memo[i] (k - 1) * (totalWays(i - 1) totalWays(i - 2)) return memo[i]!! } return totalWays(n) } }Swiftclass Solution { func numWays(_ n: Int, _ k: Int) - Int { var memo [Int: Int]() func totalWays(_ i: Int) - Int { if i 1 { return k } if i 2 { return k * k } if let val memo[i] { return val } memo[i] (k - 1) * (totalWays(i - 1) totalWays(i - 2)) return memo[i]! } return totalWays(n) } }Rustimpl Solution { pub fn num_ways(n: i32, k: i32) - i32 { let mut memo HashMap::new(); fn total_ways(i: i32, k: i32, memo: mut HashMapi32, i32) - i32 { if i 1 { return k; } if i 2 { return k * k; } if let Some(val) memo.get(i) { return val; } let result (k - 1) * (total_ways(i - 1, k, memo) total_ways(i - 2, k, memo)); memo.insert(i, result); result } total_ways(n, k, mut memo) } }时间复杂度与空间复杂度时间复杂度$O(n)$每个状态i只计算一次空间复杂度$O(n)$取决于递归调用栈深度与记忆化哈希表的大小。其中 $n$ 为栅栏柱数量。解法二自底向上动态规划填表法思路同样的递推式可以改为迭代计算从边界条件出发用数组自底向上填充到n避免递归带来的函数调用开销与栈深度问题。在实践中这种方式通常更高效因为它没有递归栈帧开销且天然按状态顺序迭代。算法步骤处理边界若n 1返回k若n 2返回k * k创建大小为n 1的数组totalWays初始化totalWays[1] k、totalWays[2] k * k对i从3到n循环计算totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2])返回totalWays[n]。多语言实现Pythonclass Solution: def numWays(self, n: int, k: int) - int: # Base cases for the problem to avoid index out of bound issues if n 1: return k if n 2: return k * k total_ways [0] * (n 1) total_ways[1] k total_ways[2] k * k for i in range(3, n 1): total_ways[i] (k - 1) * (total_ways[i - 1] total_ways[i - 2]) return total_ways[n]Javaclass Solution { public int numWays(int n, int k) { // Base cases for the problem to avoid index out of bound issues if (n 1) return k; if (n 2) return k * k; int totalWays[] new int[n 1]; totalWays[1] k; totalWays[2] k * k; for (int i 3; i n; i) { totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2]); } return totalWays[n]; } }Cclass Solution { public: int numWays(int n, int k) { // Base cases for the problem to avoid index out of bound issues if (n 1) return k; if (n 2) return k * k; int totalWays[n 1]; totalWays[1] k; totalWays[2] k * k; for (int i 3; i n; i) { totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2]); } return totalWays[n]; } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number} */ numWays(n, k) { // Base cases for the problem to avoid index out of bound issues if (n 1) return k; if (n 2) return k * k; let totalWays new Array(n 1); totalWays[1] k; totalWays[2] k * k; for (let i 3; i n; i) { totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2]); } return totalWays[n]; } }C#public class Solution { public int NumWays(int n, int k) { if (n 1) return k; if (n 2) return k * k; int[] totalWays new int[n 1]; totalWays[1] k; totalWays[2] k * k; for (int i 3; i n; i) { totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2]); } return totalWays[n]; } }Gofunc numWays(n int, k int) int { if n 1 { return k } if n 2 { return k * k } totalWays : make([]int, n1) totalWays[1] k totalWays[2] k * k for i : 3; i n; i { totalWays[i] (k - 1) * (totalWays[i-1] totalWays[i-2]) } return totalWays[n] }Kotlinclass Solution { fun numWays(n: Int, k: Int): Int { if (n 1) return k if (n 2) return k * k val totalWays IntArray(n 1) totalWays[1] k totalWays[2] k * k for (i in 3..n) { totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2]) } return totalWays[n] } }Swiftclass Solution { func numWays(_ n: Int, _ k: Int) - Int { if n 1 { return k } if n 2 { return k * k } var totalWays Int totalWays[1] k totalWays[2] k * k for i in 3...n { totalWays[i] (k - 1) * (totalWays[i - 1] totalWays[i - 2]) } return totalWays[n] } }Rustimpl Solution { pub fn num_ways(n: i32, k: i32) - i32 { if n 1 { return k; } if n 2 { return k * k; } let n n as usize; let mut total_ways vec![0; n 1]; total_ways[1] k; total_ways[2] k * k; for i in 3..n { total_ways[i] (k - 1) * (total_ways[i - 1] total_ways[i - 2]); } total_ways[n] } }时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$。其中 $n$ 为栅栏柱数量。解法三自底向上 常数空间优化思路观察递推式可知totalWays(i)只依赖totalWays(i - 1)与totalWays(i - 2)两个前序状态因此无需保存整个数组只需用两个变量滚动追踪这两个值迭代过程中不断更新即可。该优化将空间复杂度从 $O(n)$ 降到 $O(1)$。这种「滚动变量」优化思路在仓库中其他一维 DP 题解如 articles/climbing-stairs.md 的斐波那契式递推中同样适用可对照学习。算法步骤若n 1返回k初始化twoPostsBack k对应totalWays(1)、onePostBack k * k对应totalWays(2)对i从3到n计算curr (k - 1) * (onePostBack twoPostsBack)滚动移位twoPostsBack onePostBackonePostBack curr返回onePostBack。多语言实现Pythonclass Solution: def numWays(self, n: int, k: int) - int: if n 1: return k two_posts_back k one_post_back k * k for i in range(3, n 1): curr (k - 1) * (one_post_back two_posts_back) two_posts_back one_post_back one_post_back curr return one_post_backJavaclass Solution { public int numWays(int n, int k) { if (n 1) return k; int twoPostsBack k; int onePostBack k * k; for (int i 3; i n; i) { int curr (k - 1) * (onePostBack twoPostsBack); twoPostsBack onePostBack; onePostBack curr; } return onePostBack; } }Cclass Solution { public: int numWays(int n, int k) { if (n 1) return k; int twoPostsBack k; int onePostBack k * k; for (int i 3; i n; i) { int curr (k - 1) * (onePostBack twoPostsBack); twoPostsBack onePostBack; onePostBack curr; } return onePostBack; } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number} */ numWays(n, k) { if (n 1) return k; let twoPostsBack k; let onePostBack k * k; for (let i 3; i n; i) { let curr (k - 1) * (onePostBack twoPostsBack); twoPostsBack onePostBack; onePostBack curr; } return onePostBack; } }C#public class Solution { public int NumWays(int n, int k) { if (n 1) return k; int twoPostsBack k; int onePostBack k * k; for (int i 3; i n; i) { int curr (k - 1) * (onePostBack twoPostsBack); twoPostsBack onePostBack; onePostBack curr; } return onePostBack; } }Gofunc numWays(n int, k int) int { if n 1 { return k } twoPostsBack : k onePostBack : k * k for i : 3; i n; i { curr : (k - 1) * (onePostBack twoPostsBack) twoPostsBack onePostBack onePostBack curr } return onePostBack }Kotlinclass Solution { fun numWays(n: Int, k: Int): Int { if (n 1) return k var twoPostsBack k var onePostBack k * k for (i in 3..n) { val curr (k - 1) * (onePostBack twoPostsBack) twoPostsBack onePostBack onePostBack curr } return onePostBack } }Swiftclass Solution { func numWays(_ n: Int, _ k: Int) - Int { if n 1 { return k } var twoPostsBack k var onePostBack k * k for _ in 3...n { let curr (k - 1) * (onePostBack twoPostsBack) twoPostsBack onePostBack onePostBack curr } return onePostBack } }Rustimpl Solution { pub fn num_ways(n: i32, k: i32) - i32 { if n 1 { return k; } let mut two_posts_back k; let mut one_post_back k * k; for _ in 3..n { let curr (k - 1) * (one_post_back two_posts_back); two_posts_back one_post_back; one_post_back curr; } one_post_back } }时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(1)$ 常数空间。其中 $n$ 为栅栏柱数量。常见陷阱误解「三连」约束题目禁止的是超过两根连续柱子同色。部分求解者会错误地理解为「任意相邻两根都不能同色」这过于严格。实际上两根相邻柱子完全可以同色只要不出现第三根连续同色即可。正确理解这一约束才能推导出上述递推式而不是退化成k * (k - 1)^(n-1)的简单排列问题。小 n 的边界条件写错当n 1时恰好有k种方案当n 2时有k * k种方案任意组合都合法因为还不存在「连续三根」。若忽略这两个边界或计算错误不仅答案错误在填表法中还会引发数组越界index out of bounds问题。这也是三种解法都先单独处理n 1/n 2的原因。推导错误的递推关系正确递推式为totalWays(i) (k - 1) * (totalWays(i - 1) totalWays(i - 2))它精确对应两种场景第i根与第i - 1根不同色k - 1种选法乘以前i - 1根的合法方案数第i根与第i - 1根同色此时要求第i - 1与第i - 2必须不同色这部分方案数恰好等于totalWays(i - 2)同色本身只有 1 种选法。把「何时允许同色」的逻辑搞混就会得到错误的公式。三种解法对比与仓库延伸阅读解法思想时间复杂度空间复杂度适用场景自顶向下递归 记忆化递推 缓存$O(n)$$O(n)$思路直观便于讲解递推来源自底向上填表迭代填数组$O(n)$$O(n)$无递归栈开销工程上更稳自底向上常数空间滚动变量$O(n)$$O(1)$n 极大时的最优空间方案Paint Fence 是典型的一维线性 DP与本仓库收录的 articles/climbing-stairs.md爬楼梯、articles/house-robber.md打家劫舍、articles/coin-change.md零钱兑换属于同一类「由前序状态推导当前状态」的模型建议放在一起对比练习重点体会「什么时候递推式可以直接复用前两个状态、什么时候需要引入额外状态维度」。解题时从自顶向下版本入手理解递推来源再改写为常数空间版本提交是最稳妥的实战路径。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考