Thanks! Solved it now. On Feb 12, 4:20 am, "Lego Haryanto" <[EMAIL PROTECTED]> wrote: > Can be solved by dynamic programming. It can scale also even when we expand > this and introduce the 5, 6, or more coefficients. > > Think of small stuff first. We know immediately the solution of x1 = n has > only 1 solution. > > We also know that the solution of 2x2 + x1 = n will have floor(n/2) + 1 > solution (basically, trying x2 = [0,1,...floor(n/2)] ... and whatever left > of this can be solved in 1 way (see the x1 = n solution above). > > It's easy to have the solution for 2x2 + x1 = n available and let's assume > that we have this in ways[0..n-1] array. > > For number of solution for 3x3 + 2x2 + x1 = n, start with trying x3 = 0, 1, > ... floor(n/3). For x3 = 0, we have ways[n] solution, for x3 = 1, we have > ways[n-3] solution ... etc. > > Same rule applies to 4x4. > > For this, I'd prefer top down with memoization method rather than bottom up > as explained above. > > On 2/11/07, Jair Cazarin <[EMAIL PROTECTED]> wrote: > > > > > I think that a simple backtracking approach could solve this problem. > > > On 2/11/07, [EMAIL PROTECTED] < [EMAIL PROTECTED]> wrote: > > > > I`m trying to solvehttp://acm.mipt.ru/judge/problems.pl?problem=201. > > > I`ve tried googling but couldn`t get any way to approach the problem. > > > Brute force is ruled out, so how can we solve this problem? > > > >http://slipvayne.googlepages.com > > -- > Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
--~--~---------~--~----~------------~-------~--~----~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
