Sliding Window Trick
The Sliding Window Trick is a dynamic programming technique in which memory is recycled as it becomes useless. Take, for example, the Fibonacci problem. If you are using a Bottom-up Approach to calculate Fn, and you are currently calculating Fk for some k,then the only values you use to calculate Fk are Fk-1 and Fk-2. Thus, there is no reason to store previous values of the sequence. You can now reduce the memory from O(n) to O(1). Here is a java implementation:
Implementation
page revision: 5, last edited: 12 Nov 2007 05:27