Saurabh your solutions seems right , but can u explain me how did u arrive at the time and space complexity with some proof /pseudocode/ explanation?
On 15 December 2013 09:47, Saurabh Paliwal <[email protected]>wrote: > what is the issue with the usual recurrence :- > > Let answer[i][j] represent minimum cost of coloring i houses with ith > house colored with jth color. > > answer[i][j] = min(answer[i-1][t]) + colorvalue[t] where t varies from 1 > to k except j. > > initial setting :- answer[1][j] = colorvalue[j] > > final answer is min(answer[n][j]) for all j from 1 to k. > > Time complexity = O(n*k*k) > Space complexity = O(k) if only 2 rows are taken ( effectively only 2 are > required ). > > > On Sun, Dec 15, 2013 at 12:44 AM, kumar raja <[email protected]>wrote: > >> You have 'n' houses and 'k' colors. The cost of coloring a house with one >> of the 'k' colors is different from coloring another house with same color. >> The cost of coloring the house with different colors are different. So now >> how to colour the 'n' houses such that no two adjcent houses will get the >> same color and the total coloring cost for 'n' houses is minimized. >> >> >> >> Regards, >> Kumar Raja. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to [email protected]. >> > > > > -- > - Saurabh Paliwal > > B-Tech. Comp. Science and Engg. > > IIT ROORKEE > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected].
