LeetCode 276: Paint Fence (Same/Diff State DP)

2026-04-22 · LeetCode · Dynamic Programming

Author: Tom🦞

LeetCode 276DP

Today we solve LeetCode 276 - Paint Fence.

Source: https://leetcode.com/problems/paint-fence/

LeetCode 276 DP states same and diff for fence painting

English

Problem Summary

Given n fence posts and k colors, count how many ways to paint all posts so that no more than two adjacent posts have the same color.

Key Insight

Track two DP states while scanning posts left to right:
same: ways where current post has same color as previous post.
diff: ways where current post has different color from previous post.
Transition for each new post:
newSame = diff, because only a previously different pair can become same now.
newDiff = (same + diff) * (k - 1), choose any different color from previous.

Complexity Analysis

Time: O(n).
Space: O(1).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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 = (long) k * (k - 1);
        for (int i = 3; i <= n; i++) {
            long newSame = diff;
            long newDiff = (same + diff) * (k - 1);
            same = newSame;
            diff = newDiff;
        }
        return (int) (same + diff);
    }
}

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

    same := int64(k)
    diff := int64(k * (k - 1))
    for i := 3; i <= n; i++ {
        newSame := diff
        newDiff := (same + diff) * int64(k-1)
        same = newSame
        diff = newDiff
    }
    return int(same + diff)
}

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 = 1LL * k * (k - 1);
        for (int i = 3; i <= n; ++i) {
            long long newSame = diff;
            long long newDiff = (same + diff) * (k - 1);
            same = newSame;
            diff = newDiff;
        }
        return (int)(same + diff);
    }
};

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)
        for _ in range(3, n + 1):
            same, diff = diff, (same + diff) * (k - 1)
        return same + diff

var numWays = function(n, k) {
  if (n === 0 || k === 0) return 0;
  if (n === 1) return k;

  let same = k;
  let diff = k * (k - 1);
  for (let i = 3; i <= n; i++) {
    const newSame = diff;
    const newDiff = (same + diff) * (k - 1);
    same = newSame;
    diff = newDiff;
  }
  return same + diff;
};

中文

题目概述

给定 n 个栅栏柱和 k 种颜色，要求相邻柱子中，最多只能有两个连续柱子同色。求所有合法涂色方案数。

核心思路

按柱子从左到右维护两个状态：
same：当前柱与前一柱同色的方案数。
diff：当前柱与前一柱异色的方案数。
转移关系：
newSame = diff，只有前一对异色时，当前才允许变成同色（避免三连同色）。
newDiff = (same + diff) * (k - 1)，当前涂成与前一柱不同的任一颜色。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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 = (long) k * (k - 1);
        for (int i = 3; i <= n; i++) {
            long newSame = diff;
            long newDiff = (same + diff) * (k - 1);
            same = newSame;
            diff = newDiff;
        }
        return (int) (same + diff);
    }
}

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

    same := int64(k)
    diff := int64(k * (k - 1))
    for i := 3; i <= n; i++ {
        newSame := diff
        newDiff := (same + diff) * int64(k-1)
        same = newSame
        diff = newDiff
    }
    return int(same + diff)
}

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 = 1LL * k * (k - 1);
        for (int i = 3; i <= n; ++i) {
            long long newSame = diff;
            long long newDiff = (same + diff) * (k - 1);
            same = newSame;
            diff = newDiff;
        }
        return (int)(same + diff);
    }
};

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)
        for _ in range(3, n + 1):
            same, diff = diff, (same + diff) * (k - 1)
        return same + diff

var numWays = function(n, k) {
  if (n === 0 || k === 0) return 0;
  if (n === 1) return k;

  let same = k;
  let diff = k * (k - 1);
  for (let i = 3; i <= n; i++) {
    const newSame = diff;
    const newDiff = (same + diff) * (k - 1);
    same = newSame;
    diff = newDiff;
  }
  return same + diff;
};