Programming Forums - View Single Post - Techniques For Overcoming Stack Overflow In DP

Sane · Mar 28th, 2008, 8:29 PM

Agh! I got it! How could I be so silly.

Of course I can BFS and DP at the same time. To solve the subproblems in the correct order, simply traverse the completed BFS queue in reverse!

This is actually essentially the same thing as making my own stack, because just as much memory will be used. The the only difference is the problems get solved in a different order. So I could do it either way.

Finally got it after 72 hours of thought. And after all that, I think I will actually go with the custom stack.

Thanks guys.

Mar 28th, 2008, 8:29 PM	#8
Sane Banned Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 2,101 Rep Power: 6	Re: Techniques For Overcoming Stack Overflow In DP Agh! I got it! How could I be so silly. Of course I can BFS and DP at the same time. To solve the subproblems in the correct order, simply traverse the completed BFS queue in reverse! This is actually essentially the same thing as making my own stack, because just as much memory will be used. The the only difference is the problems get solved in a different order. So I could do it either way. Finally got it after 72 hours of thought. And after all that, I think I will actually go with the custom stack. Thanks guys. __________________ Looking for tough programming challenges? Try participating in Sane's Monthly Algorithms Challenges! Composing Techno is a little side hobby of mine. Techno by DJ Sane. All free for download.