276. Paint Fence

Leetcode Dynamic Programming

There is a fence with $n$ posts, each post can be painted with one of the $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.

Example:

Given n=3, k=2 return 6

      post 1,   post 2, post 3
way1    0         0       1 
way2    0         1       0
way3    0         1       1
way4    1         0       0
way5    1         0       1
way6    1         1       0

分析

假设paint[i]为有$i$个篱笆时的染色方案。可以分为两种情况：

• 最后两个篱笆颜色相同: 前$i-2$个篱笆有paint[i-2]种方案，第$i-1$个和第$i$个篱笆取相同的颜色，但是要和$i-2$个篱笆不同(题目要求不能连续超过2个篱笆颜色相同)，共有$k-1$种染色法。
• 最后两个篱笆颜色不同: 前$i-1$个篱笆有paint[i-1]种方案，第$i$个篱笆的颜色要和第$i-1$个篱笆颜色不同，还有$k-1$种方案。

由此，状态转移方程为：

paint[i] = paint[i - 1] * (k - 1) + paint[i - 2] * (k - 1);

对应的Java代码为

/**
 * @param n: non-negative integer, n posts
 * @param k: non-negative integer, k colors
 * @return: an integer, the total number of ways
 */  
public int numWays(int n, int k) {
    if (n == 1) return k;
    int[] paint = new int[n];
    paint[0] = k; paint[1] = k*k;
    for (int i = 2; i < paint.length; i++)
        paint[i] = (k - 1) * (paint[i - 1] + paint[i - 2]);
    return paint[n - 1];
}