Do you have a constrain on k? It can be done in O(k^2). Dp(p, k) would be the count the number of arrangements of size k of the previous number was p. The transitions aren't hard, there are at most three of them, you should be able to figure them out.
If you need more help, let me know, however, trying it by yourself is the way to learn it. Is k^2 is too big, well I haven't given it enough thought to know if I can or cannot do it better. Regards, Carlos Guia On Apr 2, 2012 1:28 PM, "vivek dhiman" <[email protected]> wrote: > + I am only looking at the count.. > > for k=1 ans = 1 > k=2 ans = 2 > k=3 ans = 5 > k=4 ans = 14 I guess... > k = 5 ans =52 I guess > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
