> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/dynamic_programming/sequence-dp/paint-fence.md).

# Paint Fence

## Question ([LC.276](https://leetcode.com/problems/paint-fence/description/))

> There are n posts and k colors. You have to paint all the posts such that *no more than two adjacent fence posts have the same color*.

Return the total number of ways you can paint the fence. n and k are non-zero integers.

## Example

```
(3, 2) => 6

P1 P2 P2
1  1  2
1  2  1
2  1  1
2  2  1
2  1  2
1  2  2
```

## Analysis

We only want the number of ways not the actual solutions. So we can try DP.

## Single Sequence DP

```
Step 1 Define optimal subproblem
fence(i, 0) = max number of ways to apply the same color at the ith post
fence(i, 1) = max # ways to apply different colors at the ith post

Step 2 Recurrence
fence(i, 0) = fence(i-1, 1)
fence(i, 1) = fence(i-1, 0) * (k-1) + fence(i-1, 1) * (k-1)

Step 3 Base cases
fence(0, 0) = 0
fence(0, 1) = 0
fence(1, 0) = k
fence(1, 1) = 0
fence(2, 0) = k
fence(2, 1) = k * (k - 1)
fence(3, 0) = fence(2, 1)
fence(3, 1) = fence(2, 0) * (k - 1) + fence(2, 1) * (k - 1)

Step 4 Topo Order
    for i from 3 to n

Stet 5 Final Answer
    fence(n, 0) + fence(n, 1)
```

## Code

```java
public int numWays(int n, int k) {
    // create memo table
    int adjN = n < 2 ? 2 : n;
    int[][] fence = new int[adjN + 1][2];

    // init base case
    fence[0][0] = 0;
    fence[0][1] = 0;
    fence[1][0] = k;
    fence[1][1] = 0;
    fence[2][0] = k;
    fence[2][1] = k * (k - 1);

    // topo order
    for (int i = 3; i <= n; i++) {
        fence[i][0] = fence[i-1][1];
        fence[i][1] = fence[i-1][0] * (k - 1) + fence[i-1][1] * (k - 1);
    }

    // final answer
    return fence[n][0] + fence[n][1];
}
```

There is only one layer of dependencies so we can compress the active states.

## Code w/ State Compression

```java
public int numWays(int n, int k) {
    // create memo table
    int[][] fence = new int[3][2];

    // init base case
    fence[0][0] = 0;
    fence[0][1] = 0;
    fence[1][0] = k;
    fence[1][1] = 0;
    fence[2][0] = k;
    fence[2][1] = k * (k - 1);

    // topo order
    for (int i = 3; i <= n; i++) {
        fence[i%3][0] = fence[(i-1)%3][1];
        fence[i%3][1] = fence[(i-1)%3][0] * (k - 1) + fence[(i-1)%3][1] * (k - 1);
    }

    // final answer
    return fence[n%3][0] + fence[n%3][1];
}
```

## Time Complexity

`#subproblems * time/subproblem = 2n * O(1) = O(n)`