Many people suffer with this problem solving paradigm called Dynamic Programming, one breakthrough I have made in this topic is thinking in top-down manner rather than bottom-up.

DP can be summarized in following equation

Bruteforce + memoization = DP

The Bruteforce Part

Whenever you think about recursion you think of function getting pushed and popped in the stack, that is the proper image of recursion but not the correct way of thinking about when deriving a recursive algorithm. The way I imagine is in terms of function, where I have super parallel computer. Whenever I write a recurrence, suppose F(n-1) + F(n-2) , I imagine that the universe have branched off into two parallel universe where in one universe F(n-1) is calculated and in other F(n-2) then adding them together.

Motivation Problem

There are N students standing in a line. The first student gets 1 chocolate. The second student gets 2 chocolates. The third student however demands that he gets twice as many chocolates as the first student plus the number of chocolate that the second student got. Similarly, the fourth student said that he wanted twice the amount of chocolate that the second student got plus the amount the third student got. Thus, each student wants the amount that the previous student got plus twice the amount the student before that had got. We need to find the total number of chocolate that given to the ‘x’ th student

Lets denote F(x) as the amount of chocolate the x th students got. The x th student demands the amount of chocolate x-1 th student plus twice the chocolate of x-2 th person. In terms of function it could be defined as F(x) = F(x-1) + 2 * F(x-2) .

Boom! We are done.

We can memoize the bruteforce recursive code to reduce the time complexity from exponential to polynomial. This part is left as an exercise to the reader.

Going Further

Till now we have discussed basic recurrence. We can have more complex recurrence involving more than one parameter. Read my previous blogs and answer on Quora for further knowledge.

1. https://qr.ae/TW8c67
2. https://qr.ae/TW8EO1

Reduce to One

Problem statement – https://www.codechef.com/MAY19B/problems/REDONE

It doesn’t matter whichever element we choose, answer will be same. I have come to this conclusion after observation on few testcases. Formal proof will be added later.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,s,e) for(int i=s; i<=e; i++)
#define WL(t) while(t--)
#define MAXN 1000010
#define MOD 1000000007
int dp[MAXN];
int n;
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
void precalculate() {
    dp[1] = 1;
    FOR(i,2,MAXN) {
        dp[i] = (dp[i-1] * i + dp[i-1] + i) % MOD;
    }
}
void solve() {
    cin >> n;
    cout << dp[n] << endl;
}
int32_t main() {
  __fastio;
  precalculate();
  int t; cin >> t;
  WL(t) {
    solve();
  }
  return 0;
}

Problem Statement – https://atcoder.jp/contests/dp/tasks/dp_b

This problem is similar to Frog – 1, but this time from ‘i’ we could jump to i+1, i+2, … i+K , few changes in the previous code is needed.

Implementation

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
#define FOR(i,s,e) for(int i=s; i<=e; i++)
int cost[MAXN], memo[MAXN];
int n, k;
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
int f(int i) {
    if(i > n) return INF;
    if(i == n) return 0;
    if(memo[i] != -1) return memo[i];
    else {
        int ans = INF;
        FOR(j,1,k) {
            ans = min(ans, f(i+j) + abs(cost[i] - cost[i+j]));
        }
        return memo[i] = ans;
    }
}
void solve() {
    cin >> n >> k;
    FOR(i,1,n) {
        cin >> cost[i];
    }
    memset(memo, -1, sizeof(memo));
    cout << f(1) << endl;
}
int main() {
  __fastio;
  solve();
  return 0;
}

Problem – https://atcoder.jp/contests/dp/tasks/dp_a

At every instance we have two choices, i.e either jump to ‘i+1’ th or ‘i+2’ th rock, and the cost of jumping for the former is |cost[i] – cost[i+1]| and for the latter it’s |cost[i] – cost[i+2]| and minimum of them is the answer, therefore the recurrence relation would be.

min{f(i+1) + |cost[i] – cost[i+1]| , f(i+2) + |cost[i] – cost[i+2]|}

Here, |x| denotes absolute value of ‘x’

The implementation is rather straight forward.

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100010
#define INF 1e9
#define FOR(i,s,e) for(int i=s; i<=e; i++)
int cost[MAXN], memo[MAXN];
int n;
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
int f(int i) {
    if(i > n) return INF;
    if(i == n) return 0;
    if(memo[i] != -1) return memo[i];
    return memo[i] = min(f(i+1) + abs(cost[i] - cost[i+1]), f(i+2) + abs(cost[i] - cost[i+2]));
}
void solve() {
    cin >> n;
    FOR(i,1,n) {
        cin >> cost[i];
    }
    memset(memo, -1, sizeof(memo));
    cout << f(1) << endl;
}
int main() {
  __fastio;
  solve();
  return 0;
}

Problem Statement – https://dmoj.ca/problem/ccc15j5

This problem is a multi-way choice DP problem, because we can distribute the pie in a lot of way. At first we will solve a simpler version of this, that is the number of ways we can distribute pie among people without any restriction.

Let f(n, k) denote the number of ways we can distribute ‘n’ slices to ‘k’ people, therefore recurrence will be f(n, k) = ∑ f(n-i, k-1) , here ‘n-i’ checks all the possible combination and since we distributed the slice, number of people will reduce to ‘k-1’.

Since mathematicians are a bit greedy at times. So, they always get at least as many of pieces of pie as the person in front of them.

In order to solve this, we add another parameter i.e, f(n, k, m) , where ‘m’ denotes the number of slice the last person took.

Now the recurrence will be f(n, k, m) = ∑ f(n-i, k-1, i) , and this time ‘i’ loop will be from ‘m’ to ‘n/k’. This is obvious.

Finally we memoize it to reduce the time complexity.

The Implementation is rather straight-forward

#include <bits/stdc++.h>
using namespace std;
int n, k;
int dp[255][255][255];
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
int f(int n, int k, int m) {
    if(dp[n][k][m] != -1) return dp[n][k][m];
    if(k == 1 || k == n) return 1;
    if(k > n) return 0;
    else {
        int ans = 0;
        for(int i=m; i<=n/k; i++) {
                ans += f(n - i, k - 1, i);
        }
        return dp[n][k][m] = ans;
    }
}
void solve() {
    cin >> n >> k;
    memset(dp, -1, sizeof(dp));
    cout << f(n, k, 1) << endl;
}
int main() {
  __fastio;
  solve();
  return 0;
}

Problem Statement – https://codeforces.com/problemset/problem/166/E

So we will use a DP with 2 states, that is at position D and A,B,C . Think why this optimal.

f[0][N] is the number of ways from D to D to using N steps

f[1][N] is the number of ways from A,B,C to D to using N steps

From D we can go to either A,B,C. Therefore,

f[0][N]=3∗f[1][N−1]

In order to calculate f[0][N] we need to calculate f[1][N]

From f[1][N] we could got to either at D or remaining 2 positions, Hence

f[1][N]=f[0][N−1]+2∗f[1][N−1]

So, we got to relations, i.e

f[0][N]=3∗f[1][N−1]

f[1][N]=f[0][N−1]+2∗f[1][N−1]

Base cases are

f[0][0]=1

f[1][0]=0

The Implementation is quite straight forward

#include <bits/stdc++.h>
using namespace std;
#define LL long long int
#define MOD 1000000007
#define MAX 10000010
LL F[2][MAX];
class fastio {
public:
    fastio() {
        ios_base::sync_with_stdio(false);
        cout.tie(nullptr);
        cin.tie(nullptr);
    }
} __fastio;
void solve() {
    int n; cin >> n;
    F[0][0] = 1;
    F[0][1] = 0;
    for(int i=1; i<=n; i++) {
        F[0][i] = (3 * F[1][i-1])%MOD;
        F[1][i] = (F[0][i-1] + 2*F[1][i-1])%MOD; 
    }
    cout << F[0][n]%MOD << endl;
}
int main() {
    solve();
  __fastio;
  return 0;
}