I think that can be done by having 2 different values at every position in the answer matrix. One when the previous house is of same color and one when it does not. Answer[n][k][2] will be the new dimensions.
I can explain in detail if you don't get this. ☺ On Dec 15, 2013 4:43 PM, "kumar raja" <[email protected]> wrote: > What can be the recurrence relation if the condition is changed to "No 3 > adjacent houses should get same color"? > > > On 15 December 2013 16:26, kumar raja <[email protected]> wrote: > >> No need for the explanation ,got it man thanks. >> >> >> On 15 December 2013 16:20, kumar raja <[email protected]> wrote: >> >>> 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]. > -- 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].
