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 ???