江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第276题：栅栏涂色

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱必须涂上颜色。 相邻的栅栏柱 最多连续两个 颜色相同。 给你两个整数 k 和 n ，返回所有有效涂色的方案数。答案可能很大，请返回对 10^9 + 7 取模的结果。

📖 文章摘要

本文详细解析LeetCode第276题“栅栏涂色”，这是一道经典动态规划问题。文章提供了状态转移分析和优化思路，包含C#、Python、C++三种语言实现，配有详细的状态转移表格和性能分析。适合学习动态规划状态设计的读者。

核心知识点： 动态规划、状态转移、约束条件处理
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升动态规划技能的开发者

题目描述

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱必须涂上颜色。

相邻的栅栏柱 最多连续两个 颜色相同。

给你两个整数 k 和 n ，返回所有有效涂色的方案数。答案可能很大，请返回对 10^9 + 7 取模的结果。

示例

示例 1：

输入：n = 3, k = 2
输出：6
解释：所有的可能涂色方案如下：
    柱 1    柱 2   柱 3    
    -------|-------|-------
    颜色 1  颜色 1  颜色 2
    颜色 1  颜色 2  颜色 1
    颜色 1  颜色 2  颜色 2
    颜色 2  颜色 1  颜色 1
    颜色 2  颜色 1  颜色 2
    颜色 2  颜色 2  颜色 1

示例 2：

输入：n = 1, k = 1
输出：1

示例 3：

输入：n = 7, k = 2
输出：42

提示

  • 1 <= n <= 50
  • 1 <= k <= 10^5
  • 答案对 10^9 + 7 取模

解题思路

本题可以使用动态规划来解决，关键是找到状态转移方程。我们需要考虑以下几点：

  1. 对于第i个栅栏柱，我们有两种选择：

    • 使用与前一个栅栏柱相同的颜色
    • 使用与前一个栅栏柱不同的颜色

  2. 状态定义：

    • same[i]: 第i个栅栏柱和第i-1个栅栏柱颜色相同的方案数
    • diff[i]: 第i个栅栏柱和第i-1个栅栏柱颜色不同的方案数

  3. 状态转移方程：

    • same[i] = diff[i-1] (只能从不同颜色转移到相同颜色)
    • diff[i] = (same[i-1] + diff[i-1]) * (k-1) (可以选择除了前一个颜色之外的任意颜色)

图解思路

状态转移分析表

栅栏柱位置 same[i] 计算 diff[i] 计算 总方案数 说明
i = 1 0 k k 第一个柱子可以使用任意颜色
i = 2 k k*(k-1) k + k*(k-1) 第二个柱子可以相同或不同
i = 3 k*(k-1) (k + k*(k-1))*(k-1) same[3] + diff[3] 根据状态转移方程计算

方案数计算示例表（k=2）

栅栏柱数n same diff 总方案数 具体方案示例
1 0 2 2 [1], [2]
2 2 2 4 [1,1], [1,2], [2,1], [2,2]
3 2 4 6 [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1]

代码实现

C# 实现

public class Solution {
    public int NumWays(int n, int k) {
        // 特殊情况处理
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        
        // 初始化状态数组
        long same = k;  // 第一个柱子的颜色方案数
        long diff = k * (k - 1);  // 第二个柱子与第一个柱子颜色不同的方案数
        const int MOD = 1000000007;
        
        // 从第三个柱子开始动态规划
        for (int i = 3; i <= n; i++) {
            long temp = diff;
            diff = ((same + diff) * (k - 1)) % MOD;
            same = temp;
        }
        
        return (int)((same + diff) % MOD);
    }
}

Python 实现

class Solution:
    def numWays(self, n: int, k: int) -> int:
        # 特殊情况处理
        if n == 0 or k == 0:
            return 0
        if n == 1:
            return k
            
        # 初始化状态
        same = k
        diff = k * (k - 1)
        MOD = 1000000007
        
        # 动态规划过程
        for i in range(3, n + 1):
            same, diff = diff, ((same + diff) * (k - 1)) % MOD
            
        return (same + diff) % MOD

C++ 实现

class Solution {
public:
    int numWays(int n, int k) {
        // 特殊情况处理
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        
        // 初始化状态
        long long same = k;
        long long diff = k * (k - 1);
        const int MOD = 1000000007;
        
        // 动态规划过程
        for (int i = 3; i <= n; i++) {
            long long temp = diff;
            diff = ((same + diff) * (k - 1)) % MOD;
            same = temp;
        }
        
        return (same + diff) % MOD;
    }
};

执行结果

C# 实现

  • 执行用时：24 ms
  • 内存消耗：25.1 MB

Python 实现

  • 执行用时：32 ms
  • 内存消耗：14.9 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：5.9 MB

性能对比

语言 执行用时 内存消耗 特点
C# 24 ms 25.1 MB 代码结构清晰，性能适中
Python 32 ms 14.9 MB 代码最简洁，但运行较慢
C++ 0 ms 5.9 MB 性能最优，内存占用最小

代码亮点

  1. 🎯 使用动态规划优化时间复杂度为O(n)
  2. 💡 通过same和diff两个变量优化空间复杂度为O(1)
  3. 🔍 考虑了大数据情况下的取模处理
  4. 🎨 变量命名直观，代码结构清晰

常见错误分析

  1. 🚫 忘记处理n=0或k=0的特殊情况
  2. 🚫 未考虑大数据情况下的溢出问题
  3. 🚫 状态转移方程写错，未正确处理相同颜色的限制条件
  4. 🚫 忘记对结果进行取模操作

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
动态规划（数组） O(n) O(n) 思路直观，易于理解 空间占用较大
动态规划（变量） O(n) O(1) 空间复杂度优化 代码稍难理解
递归 O(2^n) O(n) 实现简单 时间复杂度高

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第276题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！