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 F_{n}, and you are currently calculating F_{k} for some k,then the only values you use to calculate F_{k} are F_{k-1} and F_{k-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