Here is the link to the question
http://community.topcoder.com/stat?c=problem_statement&pm=6680&rd=10005
How to solve it using Dynamic Programming ?
Here is the link to the question
http://community.topcoder.com/stat?c=problem_statement&pm=6680&rd=10005
How to solve it using Dynamic Programming ?
Hi,
Use,dp[current Index][color] which is equal to the minimum cost of painting taken from current index till the end using color to paint the house at the current index.
now the recurrence simply becomes,
dp[curr Index][color] = val[curr Index][color] + min(dp[curr+1][color1], dp[curr+1][color2]);
where color1 and color2 are the colors different from current color.
Now just paint the first house R,G or B and take the minimum of those values.
Hope this helps!