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 <rajkumar.cs...@gmail.com> wrote: > No need for the explanation ,got it man thanks. > > > On 15 December 2013 16:20, kumar raja <rajkumar.cs...@gmail.com> 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 >> <saurabh.paliwa...@gmail.com>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 >>> <rajkumar.cs...@gmail.com>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 algogeeks+unsubscr...@googlegroups.com. >>>> >>> >>> >>> >>> -- >>> - 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 algogeeks+unsubscr...@googlegroups.com. >>> >> >> > -- 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 algogeeks+unsubscr...@googlegroups.com.
