LeetCode [276] Paint Fence

Note

• dp[i]: number of ways to paint i+1 fences
• dp[i] = dp[i-1]*k - dup
• dup denotes the number of ways to paint i fences while the (i-2)-th and (i-1)-th fences have the same color. 
• Thus, dup is also the number of ways to paint i+1 fences while the (i-2)-th,  (i-1)-th and i-th fences have the same color.
• Therefore, dup should be deducted from dp[i-1]*k when computing dp[i]
• When computing dp[i], dup = dp[i-2] - dp[i-3] + dp[i-4] -,...., +/- dp[0].

For 5 fences with 2 colors, 

there are two ways to paint the first fence  dp[0] = 2

         0  1  2  3  4  5

         1

         2

there are four ways to paint the first two fences   dp[1] = 4

         0  1  2  3  4  5

         1  1

         1  2

         2  1

         2  2

computing dp[2] = dp[1]*2-dup = 8 - dup. In this case, dup = dp[2-2] = dp[0] = 2. Thus, dp[2] = 6.

         0  1  2  3  4  5

         1  1  1

         1  1  2

         1  2  1

         1  2  2

         2  1  1

         2  1  2

         2  2  1

         2  2  2 

dp[3] = dp[2]*2-dup. dup =  dp[1] - dp[0] = 4-2 =2. Thus, dp[3] = 12-2 = 10;
*when computing dp[2], dp[0] illegal paintings have already been deducted. Thus, dp[0] should be deducted from dp[1] when computing the illegal paintings for dp[3].
         0  1  2  3  4  5

         1  1  2  1
         1  1  2  2

         1  2  1  1
         1  2  1  2

         1  2  2  1
         1  2  2  2

         2  1  1  1
         2  1  1  2

         2  1  2  1
         2  1  2  2

         2  2  1  1
         2  2  1  2

dp[4] = dp[3]*k - dp[2] + dp[1] - dp[0] = 20 - 6 + 4 - 2 = 16

         0  1  2  3  4  5

         1  1  2  1  1
         1  1  2  1  2
         1  1  2  2  1
         1  1  2  2  2

         1  2  1  1  1
         1  2  1  1  2
         1  2  1  2  1
         1  2  1  2  2

         1  2  2  1  1
         1  2  2  1  2

         2  1  1  2  1
         2  1  1  2  2

         2  1  2  1  1
         2  1  2  1  2
         2  1  2  2  1
         2  1  2  2  2

         2  2  1  1  1
         2  2  1  1  2
         2  2  1  2  1
         2  2  1  2  2

Ref
[1] https://leetcode.com/problems/paint-fence/ 
OJ