Dynamic programming - drawing algorithm

Question

There is a fence with n posts, each post can be painted in one of k colors. You should colorize all posts so that no more than two adjacent posts are the same color. Return the total number of ways to paint the fence.

diff - the number of combinations with different colors,
same - the number of combinations with the same colors,
n is the number of posts
k is the number of colors.

For n = 1:

diff = k; same = 0; 

For n = 2:

 diff = k * (k - 1); same = k; 

For n = 3:

 diff = (k + k * (k - 1)) * (k - 1); same = k * (k - 1); 

And the last formula:

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

I understand how to find the same[i] , but I do not understand how to find diff[i] . Can you explain the formula for diff[i] ?

Answer 1

 total[i] = diff[i] + same[i] (definition) diff[i] = (k - 1) * total[i-1] = (k - 1) * (diff[i-1] + same[i-1]) = (k - 1) * (diff[i-1] + diff[i-2]) 

Answer 2

Here is the argument of combinatorics.

Let diff[i, c] be the number of ways to paint i messages in accordance with the rules of the statement of the problem so that the last fence is colored c .

We have:

 diff[i, c] = diff[i - 1, c'] + diff[i - 2, c''], c' != c OR c'' != c 

For each c which we draw i , the previous one can either end with the symbol c' != c (in this case, we don’t care what the second previous one is), or the second previous one can end with the symbol c'' != c (in this case we all equal to the previous one) or both.

There are k - 1 possibilities for c' != c and k - 1 for c'' != c Thus, we can remove c from the repetition and simply write:

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

What do you have.

Answer 3

The solution includes a detailed explanation. Please take a look.

 public class PaintingFence { public static int paintFence(int n, int k) { //if there is 0 post then the ways to color it is 0. if(n == 0) return 0; //if there is one 1 post then the way to color it is k ways. if(n == 1) return k; /** * Consider the first two post. * case 1. When both post is of same color * first post can be colored in k ways. * second post has to be colored by same color. * So the way in which the first post can be colored with same color is k * 1. * * case 2. When both post is of diff color * first post can be colored in k ways. * second post can be colored in k-1 ways. * Hence the ways to color two post different is k * (k - 1) */ int same = k * 1; int diff = k * (k -1); /** * As first 2 posts are already discussed, we will start with the third post. * * If the first two post are same then to make the third post different, we have * k-1 ways. Hence same * (k-1) * [same=k, so same * k-1 = k*(k-1) = diff => Remember this.] * * If the first two posts are different then to make the third different, we also have * k - 1 ways. Hence diff * (k-1) * * So to make third post different color, we have * same * (k-1) + diff * (k-1) * = (same + diff) * (k-1) * = k-1 * (same + diff) */ for(int i=3;i <=n; i++) { int prevDiff = diff; diff = (same + diff) * (k - 1); //as stated above /** * to make the third color same, we cannot do that because of constraint that only two * posts can be of same color. So in this case, we cannot have to same color so it has to be * diff. */ same = prevDiff * 1; } return same + diff; } public static void main(String[] args) { System.out.println(paintFence(2, 4)); System.out.println(paintFence(3, 2)); } }