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].
