this blog will talk about the info needed to solve DP problems in general.

DP or dynamic programming is a method used to solve bigger problems be dividing them in some way

however while learning DP i recommend being similar with some data structures , sometimes we might just need a set or a map but at expert level i recommend being familiar with segment tree data structure.

this blog will be divided into phases where i explain some basic DP problems or explain some DP method in general.

each phase will contain codes and examples , you can ask more questions in comments.

Overview

1.Fibonacci

sorry for this i really know this is what people tend to explain when doing DP but hear me out

the standard Fibonacci function looked something like this

int f(int n){
   if(n<1)return 0;
   return f(n-1)+f(n-2);
}

thinking about the complexity of this code , it appears that if takes O(f(n)) time complexity.

you should know that f(40)=102334155 so we may not be able to compute f(50) or anything greater with this function!.

or.. can we do something to make this even faster?

note that computing f(i) will call f(i-1) and f(i-2) but then calling f(i-1) will also call f(i-2) , so here is the catch , lets change our function so that whenever we are computing f(n) for a second time we return the previously computed answer, something like so

int mem[N],vis[N];
int f(int n){
    if(n<1)return 0;
    if(n==1)return 1;
    if(vis[n])return mem[n];
    vis[n]=1;
    return mem[n]=f(n-1)+f(n-2);
}

what is the complexity now? , turns out it is O(N) as we may compute each item at most once and the rest will be returned in O(1).

this is the trick behind (some) DP methods , but knowing this method we will jump into some actual problems that use it.

Frog 1

no comment needed , you may just observe how similar this is to Fibonacci (or you might just jump to solve it directly).

dp(i)=min(dp(i-1)+|h(i)-h(i-1)|,dp(i-2)+|h(i)-h(i-2)|)

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=300000;
ll n,ans[N],h[N];
bool vis[N];
ll dp(int i)
{
    if(i==1)return 0;
    if(i<1)return 2e15;
    ll &res=ans[i];
    if(vis[i])return res;
    vis[i]=1;
    return res=min(dp(i-1)+abs(h[i]-h[i-1]),dp(i-2)+abs(h[i]-h[i-2]));
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    cout<<dp(n);
}

your task is now to try and solve Frog 2.

2. more conditions

previously we only needed to handle one state where as in most cases we may need more , it is really funny how some people solve DP problems with 7 states and you see their code like how are you even understanding this!.

lets go even deeper , two states it is , and the problem Vacation might be a best choice for this.

dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]
dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=300000;
ll n,a[N],b[N],c[N];
ll dp[N][3];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
    }
    cout<<max({dp[n][0],dp[n][1],dp[n][2]});
}

for(int i=1;i<=n;i++)dp(i);

3.Knapsack

this problem was really pain to understand at first , and it is not really present in the contest as long as i can see, we will now talk about Knapsack 1.

in this problem we have to compute dp(W) as the maximum profit from a capacity of W, now we need to know how to compute it using previous states , when we use an item we add ts value and subtract its weight like so

dp(W)=max(dp(W-w[i])+v[i])

but this way we may use an item more than once (the problem).

and so we may need to add extra state to know which items were used

our state will be dp[W][1<<100] (just kidding this is impossible ).

i will leave you to think on how to solve this.

for(int i=1;i<=n;i++){
    for(int j=W;j-w[i]>=0;j--){
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010;
ll n,W,w[N],v[N];
ll dp[N];
signed main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=W;j-w[i]>=0;j--){
            dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
        }
    }
    cout<<dp[W];
}

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010;
ll n,w[200],v[200],W;
ll mem[101][N];
bool vis[101][N];
ll dp(int i,int W){
    if(i==n+1)return 0;
    if(vis[i][W])return mem[i][W];
    vis[i][W]=1;
    ll &res=mem[i][W];
    res=dp(i+1,W);
    if(W-w[i]>=0){
        res=max(res,dp(i+1,W-w[i])+v[i]);
    }
    return res;
}
signed main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    cout<<dp(1,W);
}

try to solve Knapsack 2 !

4.Tracing

Ok! now we are able to find the minimum,maximum whatsoever but how do we actually know how we reached the answer? like in Knapsack how do we know what items we choose?

till now we used only two arrays mem(the answer),vis(did we calculate it before?)

now we will use another array to know from which state we got our best answer after calculating the answer we use this array to trace it.

we will present this in a simple problem like this problem this problem was solved once and i saw 2 or maybe more standard problems like it,

the state was like dp[index in S][index in T]

but knowing the transition might be hard so i will leave you to think!

int &res=ans[i][j]
if(s[i]==t[j]){
    res=dp(i+1,j+1)+1;
}
res=max({res,dp(i,j+1),dp(i+1,j)};

this way we made sure we tried all cases

we tried matching the current positions and incrementing each index by one,and so (somehow!) we can say we tried every case and got the best answer in the end!.

the code for the answer would be something like this

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010;
string s,t;
int n,m;
int ans[4000][4000],to[4000][4000],vis[4000][4000];
int dp(int i,int j){
    if(i==n||j==m)return 0;
    int &res=ans[i][j];
    if(vis[i][j])return res;
    vis[i][j]=1;
    if(s[i]==t[j]){
        to[i][j]=1;
        res=dp(i+1,j+1)+1;
    }
    if(dp(i+1,j)>res){
        to[i][j]=2;
        res=dp(i+1,j);
    }
    if(dp(i,j+1)>res){
        to[i][j]=3;
        res=dp(i,j+1);
    }
    return res;
}
void trace(int i,int j){
    if(i==n||j==m)return;
    switch(to[i][j]){
        case 1:{
            cout<<s[i];
            trace(i+1,j+1);
            break;
        }
        case 2:{
            trace(i+1,j);
            break;
        }
        case 3:{
            trace(i,j+1);
            break;
        }
    }
}
signed main(){
    cin>>s>>t;
    n=s.size();
    m=t.size();
    dp(0,0);
    trace(0,0);
}

5.Time complexity

a main issue in DP as we really need to calculate this before going forward with our solution. the time complexity is simply sum of number of operations in all states

for simplicity i usually calculate the complexity of the dp function and multiply this by the number of states (this is not precise in general)

we will go forward with an example Candies

at first glance you might think you knew the solution, but usually you will get a TLE , why?.

lets say your dp function looked like this:

for(int j=0;j<=min(a[i],k);j++){
    res+=dp(i+1,k-j);
}

what is the complexity of this?

for each dp[index][number of candies] we will loop (in worst case) on the number of candies, which means our complexity is n*k*k (an absolute disaster) we will have to get this loop in O(1) for this to work.

i recommend you try to solve it.

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010,M=1e9+7;
int n,a[200],K;
ll dp[101][N],p[101][N];
signed main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++)cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        p[i-1][0]=dp[i-1][0];
        for(int k=1;k<=K;k++)p[i-1][k]=dp[i-1][k]+p[i-1][k-1];
        for(int k=0;k<=K;k++){
            dp[i][k]=p[i-1][k];
            if(k-min(k,a[i])>0)dp[i][k]+=M-p[i-1][k-min(k,a[i])-1];
            dp[i][k]%=M;
        }
    }
    cout<<dp[n][K];
}

6.DP left right

this kind is as easy as it sounds (maybe the most unexpected answer for a problem)

you might even be able to solve the Deque problem yourself

the idea is to get the answer of an array by getting the answer of some sub arrays .

lets try to solve the problem

the state is as following:

dp[L][R][player] = dp[3000][3000][2]

knowing this we can do two transitions:

dp[L+1][R][1-player] or dp[L][R-1][1-player]

so the answer would look like:

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010,M=1e9+7;
ll n,a[3001],k;
ll mem[3001][3001][2];
bool vis[3001][3001][2];
ll dp(int L,int R,int P){
    if(L>R)return 0;
    if(vis[L][R][P])return mem[L][R][P];
    vis[L][R][P]=1;
    ll &res=mem[L][R][P];
    if(P){
        res=min(dp(L+1,R,1-P)-a[L],dp(L,R-1,1-P)-a[R]);
    }else{
        res=max(dp(L+1,R,1-P)+a[L],dp(L,R-1,1-P)+a[R]);
    }
    return res;
}
signed main(){
    cout<<fixed<<setprecision(10);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<dp(1,n,0);
}

Break

here we are actually done with standard DP

from now on we will tend to explain somethings in short and less explained way

till now the learned info is more than enough till expert level or even master level

after this there will a bunch of hard topics that are considered DP approach (each one may need a whole new blog).

you now are able to solve these:

Longest Path

Grid 1

Coins

Stones

7.DP with a trick

this trick was so amazing when i learned it

in the past we learned that DP goes in a single direction but what if the DP calls itself?

here is an example Sushi

the state of the DP here is

you may try to solve this on your own at first

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ld long double
const int N=100010,M=1e9+7;
int n,a[400],K;
ld mem[301][301][301];
bool vis[301][301][301];
ld dp(int c1,int c2,int c3){
    if(c1<0||c2<0||c3<0)return 0;
    if(c1==0&&c2==0&&c3==0)return 0;
    ld &res=mem[c1][c2][c3];
    if(vis[c1][c2][c3])return res;
    vis[c1][c2][c3]=1;
    int c0=n-c1-c2-c3;
    ld n=::n;
    res=(c1/n*(1+dp(c1-1,c2,c3))+c2/n*(1+dp(c1+1,c2-1,c3))+c3/n*(1+dp(c1,c2+1,c3-1))+c0/n)/(1-c0/n);
    return res;
}

signed main(){
    cout<<fixed<<setprecision(10);
    cin>>n;
    ll c[4]={0,0,0,0};
    for(int i=1;i<=n;i++){cin>>a[i];c[a[i]]++;}
    cout<<dp(c[1],c[2],c[3]);
}