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:


public static int fib(int n){
    int a = 1;
    int b = 1;
    for (int i = 3; i <= n; i++) { //If n>3, F,n must be calculated
        b=a+b; //Get F,i
        a=b-a; //Keep F,i-1
    return b;
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License