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

Java

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;
}

C++

C++ implementation…