Thinking should become your capital asset, no matter whatever ups and downs you come across in your life.
~ A.P.J. Abdul Kalam
Paint Fence
Welcome Back Readers!
Our next problem is "Paint Fence" of "Dynamic Programming". It is a very interesting problem. This question is a little similar to a couple of previous questions. So that's why, it is advised that you follow the sequence of questions available on our website.
If you have already solved those problems, then this one will be easy for you to understand as it will give you a broader perspective to visualize it.
Let's move to the problem.
Problem Discussion :
In this problem you are given a number n and a number k in separate lines, representing the number of fences and number of colors.
You are required to calculate and print the number of ways in which the fences could be painted so that not more than two consecutive fences have the same color.
For example:
Input: n = 5, k = 3
Output: 180
How? Well we will see that soon.
You can also check this part of the video lecture to understand it in a better way.
Approach :
Let's assume that n = 5 (number of fences), k = 3 (number of colors) and try to figure out the number of ways to paint any number of fences less than 5 starting from 1 with three different colors.
In row 1, we will store the count of all the appropriate ways in which the last 2 colors of fences are the same (representing it with ii).
In row 2, we will store the count of all the appropriate ways in which the last 2 fences are of different colors (representing it with ij).
In the third row, we will store the total count of ii and ij rows.
The problem is not defined for n = 1. Let's leave it and see for n = 2.
For ii row, and n = 2, there will be k*1 ways to paint such that the last two consecutive fences are of the same color, because there are k choices to arrange color at first position but only one choice for second position because the last two colors need to be the same.
But for ij row there will be (k*(k-1)) ways to arrange such that the last two consecutives fences are of different color, because there are k choices to arrange color at first position and (k-1) choices to arrange color at second position.
So, in column 2 there will be 3 (k*1) in row ii, 6 (k*(k-1)) in ij row and 9 in total row.(as k=3)
In column 3, row ii, in order to satisfy our condition of appropriate ways to paint such that the last two fences are of the same color, we will only consider all the ways which we listed in the last column in row ij as the last two fences were of different color. We don't consider ways to paint in ii row because that will violate the condition of no more than two fences of similar color. So there will be 6 appropriate ways.
In column 3, row ij, in order to satisfy our condition of appropriate ways to paint such that last two fences are of different color, we consider all the ways which we listed in last column in row ij and ii as whether the last two fences were of different or same color doesn't matter because now we will add a different color which will not violate the condition. But since we have two options left to choose from there will be twice the total ways. That is 18 in this case.
In the same way we try to fill our further rows of further columns.
You can try to fill this table further yourself and then cross check it with the figure. You can also watch this part of the video for more clear understanding.
Let's give it a try and try to code this.
We use long because of the constraints given in the problem.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int k = scn.nextInt();
long[] dp = new long[n + 1];
long same = k * 1;
long diff = k * (k-1);
long total = same + diff;
for(int i = 3; i <= dp.length; i++){
same = diff * 1; e
diff = total * (k - 1);
toatl = same + diff;
}
System.out.println(total);
}
}
java;
true";
We use long because of the constraints given in the problem.
Analysis
Time Complexity :
The time complexity of this procedure is O(n) where n is the length of an array.
SPACE COMPLEXITY :
Since we have used two integer variables which take constant space, instead of two arrays of size n + 1, hence we are able to reduce the space complexity from O(n ) to O(1) also we have not used any extra memory or any extra data structure.
We hope that this article was helpful. You must check out our solution video for more clear understanding. We want you to dry run your code for different values of n and k.
Thought process of this question resembles a couple of previous problems which we have already discussed. Also if you remember about permutation and combination then understanding this kind of problem will be beneficial.
Forgive yourself and stay focused. Until then keep thinking and solving new problems on Dynamic Programming. All the best!
