Dynamic Programming

Brief

DP - Those who cannot remember the past are condemned to repeat it.

Approaches

Dynamic programming we solve using the following 2 approaches. For any problem we go from the memoization to tabulation and followedby optimization of space.

Memoization

• Top-down

• from n to base condition

Tabulation

• Bottom-up

• from base condition to n

Optimize the space

• Optimizing space on top of the tabulation approach

Example - Fibonacii

Recurssion

void f(int n){
    if (n<=1) return n;

    return f(n-1) + f(n-2);
}

Memoization

void f(int n, int[] dp){
    if (n<=1) return n;

    if(dp[n]!=-1) return dp[n];

    dp[n] = f(n-1) + f(n-2);

    return dp[n];
}

Tabulation

Copy the same condition from the memoization into the tabulation for loop.

dp[0] = 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
    dp[i] = dp[n-1] + dp[n-2]
}

Tabulation - space optimization

int prev1 = 1;
int prev2 = 0;
int curr = 0;
for(int i=2; i<=n; i++){
    curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
}