he first few f(i): f(1)=0 f(2)=max(f(1)+f(1-1+1)+1) = 1 f(3)=max{f(1)+f(2)+1, f(2)+f(1)+1} = 2 f(4)=max{f(1)+f(3)+1, f(2)+f(2)+1, f(3)+f(1)+1} =3 f(5)=max{f(1)+f(4)+1, f(2)+f(3)+1, ....,f(4)+f(1)+1} = 4 f(6)=max{.....} =5
what I can see here is in each f(i), all comma separated expressions evaluate to the same value. For exampe in f(5), all f(1)+f(4)+1, f(2)+f(3)+1....evaluate to same value 4. so by inspection it is easy to see that the answer is: f(n+1) = n, for all n. This can be generalized on the base case to: f(n+1) = (n+1)*f(1) + n. But, how to go to prove such a thing formally? On Feb 16, 8:45 pm, Vikas Kumar <dev.vika...@gmail.com> wrote: > f(n)=n-1. > > On Wed, Feb 16, 2011 at 7:39 PM, Akshata Sharma > <akshatasharm...@gmail.com>wrote: > > > please help.. > > > if f(n+1) = max{ f(k) + f(n-k+1) + 1} for 1 <= k <= n; f(1) = 0. > > Find f(n+1) in terms of n. > > Eg: f(4) = ? n = 3; 1<= k <= 3; f(4) = max{f(1) + f(3) + 1, f(2) + > > f(2)+1, f(3) + f(1) +1} > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.