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