Given a line of n houses where the color of the first house and nth house is fixed, find the number of ways to color the houses if given k colors in total where no adjacent houses can have same color.
One approach could be ways[i][color] is the number of ways to color ith index with a color. where 1 <= color <= k
Transition would be :
ways[i][color] += ways[i-1][color_prev] where 1 <= color , color_prev <= k and color_prev != color
What is a more optimised approach for O(n) probably ???
First we can observe that given the color of house 1 is fixed, there are $$$(k-1)^{(i-1)}$$$ ways to color the first i houses while avoiding adjacent houses with the same color, not considering the constraint on house n (for each house after the first we can pick from any color except the one that was just used). Let's call this quantity $$$t_i$$$.
Let $$$dp[i]$$$ be the number of ways to color the first i houses while avoiding adjacent houses with the same color, where house i has the same color as house 1. Then we have base case $$$dp[1]=1$$$ and $$$dp[i] = t_{i-1} - dp[i-1]$$$.
If the first and the last houses are fixed with the same color, then the answer is just $$$dp[n]$$$. Otherwise it's $$$\frac{t_n-dp[n]}{k-1}$$$ as the remaining arrangements are evenly split among all remaining colors
Hi can you please explain how to calculate the t[i] based on t[i-1]. Thank you .
We have to only multiply t[i-1] by (k-1) since only i is increased.
dynamic programng