Paint Fence

• Easy
• keyword: DP, 循环引用的状态数组解决DP
• 类似: BTBSS4, maximum subarray product

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.

idea

• 先是分析题目, 看上去组合类题目, 那么可以遍历或者记忆化搜索: DP.

• 这里的要求是最多2个连续的post刷一个颜色. 所以对于DP, 就通过对当前这个post来判断. 即这个post和前一个post有2种情况:

  1. 同色, 那么pre就不能和pre的pre同色了.
  2. 不同色, 那么pre和pre的pre又有2种: 同色/不同色. 所以像Best time to buy and sell stock IV, 或者是maximum subarray products那样分成2个互相作用的DP数组: l2SC[n+1], l2DC[n+1]. 分别表示最后2个same color的方案总数/different color的方案总数.

  3. 那么他们的关系是什么呢? BTBSS4的就比较复杂, 要好好理解. 这里还是比较简单的:

     • $$l2SC[n] = l2DC[n-1] * 1$$;
     • $$l2DC[n] = l2DC[n-1] (k-1) + l2SC[n-1] (k-1)$$.

  4. DP的4大要素: state, function, Initialization, answer. 已经写好了前2个.

     • Initialization的话: l2SC[0] = -1. 即无意义, l2SC[1] = k, l2SC[2] = k; l2DC[1] = k, l2DC[2] = k * (k-1).
     • answer即最大的state: l2SC[n] + l2DC[n]

代码

public int numWays(int n, int k) {
    if (n == 0) {  // edge case: if 0, l2DC is not valid
      return 0;
    }
    if (n == 1) {  // edge case: there is no last 2 diff color!
      return k;
    }
    int[] l2DC = new int[2];
    int[] l2SC = new int[2];
    l2DC[0] = 0;
    l2DC[1] = k;
    l2DC[2%2] = k * (k-1);

    l2SC[0] = 0;
    l2SC[1] = k;
    l2SC[2%2] = k * 1;

    for (int i = 3; i < n+1; ++i) {
      //F[i] = F[i-1] * (k-1) + F[i-1] * (k-2) + F[i-1] * (k-1);
      l2DC[i%2] = (l2SC[(i-1)%2] + l2DC[(i-1)%2]) * (k-1);
      l2SC[i%2] = l2DC[(i-1)%2] * 1; //(k-1);
    }

    return l2DC[n%2] + l2SC[n%2];
  }

分析

• 上面的代码是通过先写出O(2N)的空间复杂度之后, 由于状态只和上一个状态有关, 所以可以通过rolling array来优化到O(4)的空间复杂度.
• 时间复杂度显然O(N).

优化

• 这里记住背包九讲的trick: init为0则是背包可以不满, -1则是必须满.
• 还有空间优化可以更好, 因为只和上一个状态有关, 直接顺序update 2个var即可, 不需要使用array. 所以是O(2)的复杂度.