LeetCode 276. 栅栏涂色

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：数学公式推导
相似题目

题目描述

✅ 276. 栅栏涂色

思路分析

解法一：动态规划（推荐）

核心思路：

设 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]

边界：same[1] = 0，diff[1] = k

复杂度分析：

时间复杂度：O(n)，其中 n 为柱子数量

空间复杂度：O(1)，滚动变量优化

class Solution {
  public int numWays(int n, int k) {
    if (n == 0) {
      return 0;
    }
    if (n == 1) {
      return k;
    }

    // same：当前柱子与前一根同色的方案数
    // diff：当前柱子与前一根不同色的方案数
    int same = 0;
    int diff = k;

    for (int i = 2; i <= n; i++) {
      int newSame = diff;
      int newDiff = (same + diff) * (k - 1);

      same = newSame;
      diff = newDiff;
    }

    return same + diff;
  }
}

func numWays(n int, k int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return k
    }

    // same：当前柱子与前一根同色的方案数
    // diff：当前柱子与前一根不同色的方案数
    same := 0
    diff := k

    for i := 2; i <= n; i++ {
        newSame := diff
        newDiff := (same + diff) * (k - 1)

        same = newSame
        diff = newDiff
    }

    return same + diff
}

解法二：数学公式推导

核心思路：

第一根柱子有 k 种选择

第 i 根（i >= 2）柱子：只要不与第 i-1 根相同即可（不限制与 i-2 的关系），有 k-1 种选择

但需保证不连续三根相同，因此直接公式无法覆盖此约束，需用 DP 的 same/diff 分类

等价推导：total[i] = (k-1) * (total[i-1] + total[i-2])

初始值：total[1] = k，total[2] = k * k（无三连约束时），但配合分类更直观

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
  public int numWays(int n, int k) {
    if (n == 0) {
      return 0;
    }
    if (n == 1) {
      return k;
    }

    // 利用递推：total[i] = (k-1) * (total[i-1] + total[i-2])
    int prev2 = k;
    int prev1 = k * k;

    for (int i = 3; i <= n; i++) {
      int cur = (k - 1) * (prev1 + prev2);

      prev2 = prev1;
      prev1 = cur;
    }

    return prev1;
  }
}

func numWays(n int, k int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return k
    }

    // 利用递推：total[i] = (k-1) * (total[i-1] + total[i-2])
    prev2 := k
    prev1 := k * k

    for i := 3; i <= n; i++ {
        cur := (k - 1) * (prev1 + prev2)

        prev2 = prev1
        prev1 = cur
    }

    return prev1
}

相似题目

题目	难度	考察点
70. 爬楼梯	简单	动态规划
198. 打家劫舍	中等	动态规划
213. 打家劫舍 II	中等	动态规划
256. 粉刷房子	中等	动态规划
265. 粉刷房子 II	困难	动态规划
740. 删除并获得点数	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/45528186