How to Solve it using DP

general
,
1

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 ?

1 Like
2

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!

2 Likes