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](https://atcoder.jp/contests/dp/tasks/dp_a)↵
↵
no comment needed , you may just observe how similar this is to Fibonacci (or you might just jump to solve it directly).↵
↵
<spoiler summary="The solution">↵
the state of our DP contains one integer, the position we wanna reach , and so ↵
↵
```↵
dp(i)=min(dp(i-1)+|h(i)-h(i-1)|,dp(i-2)+|h(i)-h(i-2)|)↵
```↵
we may write this in simple code like so↵
↵
<spoiler summary="c++ top down">↵
```↵
#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);↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
your task is now to try and solve [Frog 2](https://atcoder.jp/contests/dp/tasks/dp_b).↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_c) might be a best choice for this.↵
↵
<spoiler summary="the solution">↵
this will include calculating $dp[n][3]$ where the state will also contain what we did on the last day .↵
so ↵
↵
```↵
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];↵
```↵
a simple implementation would look like this:↵
↵
<spoiler summary="c++ bottom up">↵
```↵
#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]});↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="i recommend you seeing the previous solutions">↵
notice how the first solution is top down as of the second is bottom up.↵
↵
by top down i mean using a recursive function and the current state waits other states till they finish computing their answer , this may take some additional time in general (and may lead to TLE in some hard problems) , top down puts a pressure on the stack used to handle recursion (worth mentioning), as of simple problems of like this it is okay to use recursion .↵
↵
NOTE that you can cancel recursion by calling the DP function in the same direction of computation↵
↵
for example in Frog 1↵
↵
```↵
for(int i=1;i<=n;i++)dp(i);↵
```↵
↵
will cancel the recursion and will be as much as if we did bottom up approach .↵
↵
i really like bottom up , but i will try to make my codes more creative.↵
</spoiler>↵
↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_d).↵
↵
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][2^100]$ (just kidding this is impossible ).↵
↵
i will leave you to think on how to solve this.↵
↵
<spoiler summary="the solution">↵
the solution consists of an array $dp[W]$↵
which will contain the solution of each weight ↵
and we will loop the items one by one doing the following:↵
↵
```↵
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]);↵
}↵
}↵
```↵
↵
note that the loop j goes from the end to the beginning (for a reason).↵
this is because if we go from the beginning to the end the current item might be used more than once ↵
↵
just think about it the current item $w[i]=2$ $v[i]=3$↵
then if we go from the beginning the answers will be $dp[2]=3$ and $dp[4]=6$.↵
↵
the final code would be↵
↵
<spoiler summary="c++">↵
```↵
#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];↵
}↵
```↵
</spoiler>↵
↵
try to solve this using top down approach!↵
↵
<spoiler summary="Hint!">↵
the state is dp[current weight][current item]↵
</spoiler>↵
↵
↵
<spoiler summary="top down code">↵
```↵
#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);↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
try to solve [Knapsack 2](https://atcoder.jp/contests/dp/tasks/dp_e) !↵
↵
<spoiler summary="Hint!">↵
calculate the minimum weight needed for each value instead!↵
</spoiler>↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_f)↵
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!↵
↵
<spoiler summary="the transitions">↵
```↵
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)};↵
```↵
</spoiler>↵
↵
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↵
↵
<spoiler summary="c++">↵
```↵
#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);↵
}↵
```↵
↵
↵
</spoiler>↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_m)↵
↵
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 $nk^2$ (an absolute disaster) we will have to get this loop in $O(1)$ for this to work.↵
↵
i recommend you try to solve it.↵
↵
<spoiler summary="Hint!">↵
prefix sum?↵
</spoiler>↵
↵
↵
<spoiler summary="the solution">↵
for me i will build the solution using bottom up approach↵
↵
lets calculate $dp[i][k]$ as the number of ways to distribute $k$ candies on the first $i$ persons.↵
↵
we will first set base case as $dp[0][0]=1$ , otherwise there will be left overs and this case is rejected.↵
and then ↵
↵
$$↵
dp[i][k]=\sum_{j=0}^{min(k,a[i])} dp[i-1][k-j]↵
$$↵
↵
so lets just build another array along with this that contains prefix sum on the second state like so↵
↵
<spoiler summary="c++">↵
```↵
#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];↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_l) 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:↵
↵
<spoiler summary="spoiler">↵
```↵
dp[L][R][player] = dp[3000][3000][2]↵
```↵
</spoiler>↵
↵
knowing this we can do two transitions:↵
↵
<spoiler summary="spoiler">↵
```↵
dp[L+1][R][1-player] or dp[L][R-1][1-player]↵
```↵
with some calculations↵
</spoiler>↵
↵
so the answer would look like:↵
↵
<spoiler summary="c++">↵
```↵
#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);↵
}↵
```↵
</spoiler>↵
↵
another good example on this would be [Slimes](https://atcoder.jp/contests/dp/tasks/dp_n)↵
↵
try to solve it yourself the continue.↵
↵
<spoiler summary="spoiler">↵
the state is dp[L][R]↵
starting from dp[1][n]↵
↵
we will solve the problem in reverse, imagine we reached the last element , its value would be the sum of the array , so this would eventually be added to the answer,and choose two consecutive sub arrays , and add their answer.↵
$$↵
dp[i][i]=0↵
$$↵
$$↵
dp[L][R]=(\sum_{i=L}^R a[i])+min(dp[L][j]+dp[j+1][R]) \forall L \le j \le R-1↵
$$↵
↵
try to code it yourself :).↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_g)↵
↵
[Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)↵
↵
[Coins](https://atcoder.jp/contests/dp/tasks/dp_i)↵
↵
<spoiler summary="Hint!">↵
the state is dp[current coin][number of heads we got]↵
</spoiler>↵
↵
[Stones](https://atcoder.jp/contests/dp/tasks/dp_k)↵
↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_j)↵
↵
the state of the DP here is ↵
↵
<spoiler summary="spoiler">↵
$dp[number of plates with 1 sushi][2 sushis][3 sushis] =dp[c1][c2][c3]$↵
note that we can get number of plates with $0$ sushis by subtracting $c1$ $c2$ $c3$ from $n$↵
</spoiler>↵
↵
you may try to solve this on your own at first↵
↵
<spoiler summary="the solution">↵
a simple transition would look like↵
$c0=n-c1-c2-c3$↵
$$↵
dp[c1][c2][c3]=\frac{c1}{n}(1+dp[c1-1][c2][c3])↵
+\frac{c2}{n}(1+dp[c1+1][c2-1][c3])↵
+\frac{c3}{n}(1+dp[c1][c2+1][c3-1])↵
$$↵
$$↵
+\frac{c0}{n}(1+dp[c1][c2][c3])↵
$$↵
↵
the last line shows how we returned to the current state which is not right, so we must do something.↵
↵
watch this↵
$$↵
dp[c1][c2][c3]-\frac{c0}{n}dp[c1][c2][c3]=\frac{c1}{n}(1+dp[c1-1][c2][c3])↵
+\frac{c2}{n}(1+dp[c1+1][c2-1][c3])↵
$$↵
$$↵
+\frac{c3}{n}(1+dp[c1][c2+1][c3-1])↵
+\frac{c0}{n}↵
$$↵
↵
↵
↵
$$↵
dp[c1][c2][c3]=\frac{\frac{c1}{n}(1+dp[c1-1][c2][c3])↵
+\frac{c2}{n}(1+dp[c1+1][c2-1][c3])↵
+\frac{c3}{n}(1+dp[c1][c2+1][c3-1])↵
+\frac{c0}{n}}{1-\frac{c0}{n}}↵
$$↵
↵
and that's the trick :).↵
↵
this is present in a lot (really a a lot) of atcoder beginner contest E,F problems and really popular but rarely taught anywhere.↵
↵
<spoiler summary="c++">↵
```↵
#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]);↵
}↵
```↵
</spoiler>↵
↵
↵
</spoiler>↵
↵
8.DP bitmask↵
------------------↵
↵
here a bitmask is chosen to identify if an element is used or not , we may use this in a lot of ways , i remember using a bitmask of $3^n$ or even $4^n$ but let's focus now on $2^n$↵
↵
let's solve this problem [Matching](https://atcoder.jp/contests/dp/tasks/dp_o).↵
↵
<spoiler summary="the state">↵
dp[current guy][bitmask of choosen girls]=dp[21][1<<21]↵
</spoiler>↵
↵
<spoiler summary="the transition">↵
for each girl try to match it with the current guy if possible (the girl was not chosen and they are compatible).↵
</spoiler>↵
↵
<spoiler summary="the code">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll int64_t↵
#define ld long double↵
const int N=100010,M=1e9+7;↵
ll mem[21][1<<21];↵
int vis[21][1<<21];↵
ll n;↵
bool comp[21][21];↵
ll dp(int i,int m){↵
if(i==n)return 1;↵
if(vis[i][m])return mem[i][m];↵
vis[i][m]=1;↵
ll &res=mem[i][m];↵
for(int j=0;j<n;j++){↵
if((m>>j)&1)continue;↵
if(!comp[i][j])continue;↵
res+=dp(i+1,m|(1<<j));↵
}↵
res%=M;↵
return res;↵
}↵
signed main(){↵
cin>>n;↵
for(int i=0;i<n;i++){↵
for(int j=0;j<n;j++)cin>>comp[i][j];↵
}↵
cout<<dp(0,0);↵
↵
}↵
```↵
</spoiler>↵
↵
what is the time complexity of this code?↵
↵
<spoiler summary="the answer">↵
do not mistake the mistake of $n^22^n$↵
the time complexity in worst case (where the whole array is ones) is:↵
$$↵
\sum_{j=0}^{n-1} n\binom{n}{j}↵
$$↵
which in worst case $n=21$ would be $44039730$↵
</spoiler>↵
↵
↵
9.DP on tree↵
------------------↵
↵
the most annoying kind especially with re rooting , lets focus on the main idea.↵
↵
in this kind of dp you must chose a root and calculate the result of each node depending on its children.↵
↵
like in the [Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p) problem.↵
↵
the state of the dp is $dp[node][color]$ so if the current color is black you consider the answer of $dp[child][white]$ , otherwise you consider both $dp[child][white]$ and $dp[child][black]$↵
↵
note that we must multiply the childrens answer (not add)↵
↵
<spoiler summary="c++">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll int64_t↵
#define ld long double↵
#define pb push_back↵
const int N=100010,M=1e9+7;↵
ll n;↵
vector<int> adj[N];↵
bool vis[N][2];↵
ll mem[N][2];↵
ll dp(int i,int d,int c){↵
if(vis[i][c])return mem[i][c];↵
vis[i][c]=1;↵
ll &res=mem[i][c];↵
res=1;↵
int cn=0;↵
for(int j:adj[i]){↵
if(j==d)continue;↵
cn++;↵
if(c==0){//it is white↵
res*=(dp(j,i,1)+dp(j,i,0));↵
}else{↵
res*=dp(j,i,0);↵
}↵
res%=M;↵
}↵
return res;↵
}↵
signed main(){↵
cin>>n;↵
for(int i=1,x,y;i<n;i++){↵
cin>>x>>y;↵
adj[x].pb(y);↵
adj[y].pb(x);↵
}↵
cout<<(dp(1,1,0)+dp(1,1,1))%M;↵
}↵
```↵
</spoiler>↵
↵
10.DP with segment tree↵
------------------↵
↵
this kind of DP is almost always deduced as we only need to know segment trees so solve this.↵
↵
some times we only need to find minimum or maximum in range to solve them .↵
↵
a good example would be [Flowers](https://atcoder.jp/contests/dp/tasks/dp_q)↵
↵
in this problem we must chose an increasing sub sequence of heights such that the sum of values as maximum ↵
↵
we can solve it for each index from $1$ to $n$ get the maximum answer among all heights that are less than $h(i)$ and add the value of the current flower to it and then update this value in the segment tree.↵
↵
the solution is left to the reader :).↵
↵
11. DP with matrices↵
------------------↵
↵
if you do know matrices you really should not be reading this as all matrices problems are DP in fact, but you might have fun solving [Walk](https://atcoder.jp/contests/dp/tasks/dp_r)↵
↵
Note that i might make a tutorial about matrices some day! stay tuned :).↵
↵
↵
12.digit DP↵
------------------↵
↵
this is one of the most annoying because if you made a mistake debugging is impossible.↵
↵
problems of digit DP give you two numbers a,b such that their values are really huge (up to $10^{100000}$) and ask you to count how many numbers between them satisfies something.↵
↵
in the problem [Digit Sum](https://atcoder.jp/contests/dp/tasks/dp_s).↵
↵
this is a not really easy problem , and the state is more annoying↵
↵
↵
<spoiler summary="the state">↵
$dp$[index][are we sure we are greater than a?][are we sure we are less than b?][mod on D]=$dp[N][2][2][100]$↵
we can just imagine filling digits in our current value.↵
</spoiler>↵
↵
<spoiler summary="the transition">↵
in the transition we add an integer digit , but what can we add?↵
traversing the digits from left to right (bigger values) because the decide what we can do later↵
using this code:↵
↵
```↵
if(we are sure we are greater than a)L=0;↵
else↵
L=a[i]-'0'↵
if(we are sure we are less than b)R=9;↵
else R=b[i]-'0';↵
```↵
</spoiler>↵
↵
so our solution is:↵
↵
<spoiler summary="c++">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll int64_t↵
#define ld long double↵
#define pb push_back↵
const int N=10010,M=1e9+7;↵
string a,b;↵
ll D;↵
ll mem[N][2][2][100];↵
int vis[N][2][2][100];↵
ll dp(int i,int bl,int br,int md){↵
if(i==a.size())return md==0;↵
if(vis[i][bl][br][md])return mem[i][bl][br][md];↵
vis[i][bl][br][md]=1;↵
ll &res=mem[i][bl][br][md];↵
int L=a[i]-'0',R=b[i]-'0';↵
if(bl)L=0;↵
if(br)R=9;↵
for(int j=L;j<=R;j++){↵
res+=dp(i+1,bl|(j>L),br|(j<R),(md+j)%D);↵
}↵
res%=M;↵
return res;↵
}↵
↵
signed main(){↵
cin>>b;↵
a=string(b.size()-1,'0')+"1";↵
cin>>D;↵
cout<<dp(0,0,0,0);↵
}↵
```↵
</spoiler>↵
↵
and i think that's it as much as i would like to solve more , but i think i will leave it to you to view more and more dp problems , thank you for reading :).↵
↵
↵
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.↵
↵
==================↵
↵
↵
------------------↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_a)↵
↵
no comment needed , you may just observe how similar this is to Fibonacci (or you might just jump to solve it directly).↵
↵
<spoiler summary="The solution">↵
the state of our DP contains one integer, the position we wanna reach , and so ↵
↵
```↵
dp(i)=min(dp(i-1)+|h(i)-h(i-1)|,dp(i-2)+|h(i)-h(i-2)|)↵
```↵
we may write this in simple code like so↵
↵
<spoiler summary="c++ top down">↵
```↵
#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);↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
your task is now to try and solve [Frog 2](https://atcoder.jp/contests/dp/tasks/dp_b).↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_c) might be a best choice for this.↵
↵
<spoiler summary="the solution">↵
this will include calculating $dp[n][3]$ where the state will also contain what we did on the last day .↵
so ↵
↵
```↵
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];↵
```↵
a simple implementation would look like this:↵
↵
<spoiler summary="c++ bottom up">↵
```↵
#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]});↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="i recommend you seeing the previous solutions">↵
notice how the first solution is top down as of the second is bottom up.↵
↵
by top down i mean using a recursive function and the current state waits other states till they finish computing their answer , this may take some additional time in general (and may lead to TLE in some hard problems) , top down puts a pressure on the stack used to handle recursion (worth mentioning), as of simple problems of like this it is okay to use recursion .↵
↵
NOTE that you can cancel recursion by calling the DP function in the same direction of computation↵
↵
for example in Frog 1↵
↵
```↵
for(int i=1;i<=n;i++)dp(i);↵
```↵
↵
will cancel the recursion and will be as much as if we did bottom up approach .↵
↵
i really like bottom up , but i will try to make my codes more creative.↵
</spoiler>↵
↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_d).↵
↵
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][2^100]$ (just kidding this is impossible ).↵
↵
i will leave you to think on how to solve this.↵
↵
<spoiler summary="the solution">↵
the solution consists of an array $dp[W]$↵
which will contain the solution of each weight ↵
and we will loop the items one by one doing the following:↵
↵
```↵
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]);↵
}↵
}↵
```↵
↵
note that the loop j goes from the end to the beginning (for a reason).↵
this is because if we go from the beginning to the end the current item might be used more than once ↵
↵
just think about it the current item $w[i]=2$ $v[i]=3$↵
then if we go from the beginning the answers will be $dp[2]=3$ and $dp[4]=6$.↵
↵
the final code would be↵
↵
<spoiler summary="c++">↵
```↵
#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];↵
}↵
```↵
</spoiler>↵
↵
try to solve this using top down approach!↵
↵
<spoiler summary="Hint!">↵
the state is dp[current weight][current item]↵
</spoiler>↵
↵
↵
<spoiler summary="top down code">↵
```↵
#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);↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
try to solve [Knapsack 2](https://atcoder.jp/contests/dp/tasks/dp_e) !↵
↵
<spoiler summary="Hint!">↵
calculate the minimum weight needed for each value instead!↵
</spoiler>↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_f)↵
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!↵
↵
<spoiler summary="the transitions">↵
```↵
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)};↵
```↵
</spoiler>↵
↵
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↵
↵
<spoiler summary="c++">↵
```↵
#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);↵
}↵
```↵
↵
↵
</spoiler>↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_m)↵
↵
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 $nk^2$ (an absolute disaster) we will have to get this loop in $O(1)$ for this to work.↵
↵
i recommend you try to solve it.↵
↵
<spoiler summary="Hint!">↵
prefix sum?↵
</spoiler>↵
↵
↵
<spoiler summary="the solution">↵
for me i will build the solution using bottom up approach↵
↵
lets calculate $dp[i][k]$ as the number of ways to distribute $k$ candies on the first $i$ persons.↵
↵
we will first set base case as $dp[0][0]=1$ , otherwise there will be left overs and this case is rejected.↵
and then ↵
↵
$$↵
dp[i][k]=\sum_{j=0}^{min(k,a[i])} dp[i-1][k-j]↵
$$↵
↵
so lets just build another array along with this that contains prefix sum on the second state like so↵
↵
<spoiler summary="c++">↵
```↵
#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];↵
}↵
```↵
</spoiler>↵
↵
</spoiler>↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_l) 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:↵
↵
<spoiler summary="spoiler">↵
```↵
dp[L][R][player] = dp[3000][3000][2]↵
```↵
</spoiler>↵
↵
knowing this we can do two transitions:↵
↵
<spoiler summary="spoiler">↵
```↵
dp[L+1][R][1-player] or dp[L][R-1][1-player]↵
```↵
with some calculations↵
</spoiler>↵
↵
so the answer would look like:↵
↵
<spoiler summary="c++">↵
```↵
#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);↵
}↵
```↵
</spoiler>↵
↵
another good example on this would be [Slimes](https://atcoder.jp/contests/dp/tasks/dp_n)↵
↵
try to solve it yourself the continue.↵
↵
<spoiler summary="spoiler">↵
the state is dp[L][R]↵
starting from dp[1][n]↵
↵
we will solve the problem in reverse, imagine we reached the last element , its value would be the sum of the array , so this would eventually be added to the answer,and choose two consecutive sub arrays , and add their answer.↵
$$↵
dp[i][i]=0↵
$$↵
$$↵
dp[L][R]=(\sum_{i=L}^R a[i])+min(dp[L][j]+dp[j+1][R]) \forall L \le j \le R-1↵
$$↵
↵
try to code it yourself :).↵
↵
</spoiler>↵
↵
↵
↵
↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_g)↵
↵
[Grid 1](https://atcoder.jp/contests/dp/tasks/dp_h)↵
↵
[Coins](https://atcoder.jp/contests/dp/tasks/dp_i)↵
↵
<spoiler summary="Hint!">↵
the state is dp[current coin][number of heads we got]↵
</spoiler>↵
↵
[Stones](https://atcoder.jp/contests/dp/tasks/dp_k)↵
↵
↵
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](https://atcoder.jp/contests/dp/tasks/dp_j)↵
↵
the state of the DP here is ↵
↵
<spoiler summary="spoiler">↵
$dp[number of plates with 1 sushi][2 sushis][3 sushis] =dp[c1][c2][c3]$↵
note that we can get number of plates with $0$ sushis by subtracting $c1$ $c2$ $c3$ from $n$↵
</spoiler>↵
↵
you may try to solve this on your own at first↵
↵
<spoiler summary="the solution">↵
a simple transition would look like↵
$c0=n-c1-c2-c3$↵
$$↵
dp[c1][c2][c3]=\frac{c1}{n}(1+dp[c1-1][c2][c3])↵
+\frac{c2}{n}(1+dp[c1+1][c2-1][c3])↵
+\frac{c3}{n}(1+dp[c1][c2+1][c3-1])↵
$$↵
$$↵
+\frac{c0}{n}(1+dp[c1][c2][c3])↵
$$↵
↵
the last line shows how we returned to the current state which is not right, so we must do something.↵
↵
watch this↵
$$↵
dp[c1][c2][c3]-\frac{c0}{n}dp[c1][c2][c3]=\frac{c1}{n}(1+dp[c1-1][c2][c3])↵
+\frac{c2}{n}(1+dp[c1+1][c2-1][c3])↵
$$↵
$$↵
+\frac{c3}{n}(1+dp[c1][c2+1][c3-1])↵
+\frac{c0}{n}↵
$$↵
↵
↵
↵
$$↵
dp[c1][c2][c3]=\frac{\frac{c1}{n}(1+dp[c1-1][c2][c3])↵
+\frac{c2}{n}(1+dp[c1+1][c2-1][c3])↵
+\frac{c3}{n}(1+dp[c1][c2+1][c3-1])↵
+\frac{c0}{n}}{1-\frac{c0}{n}}↵
$$↵
↵
and that's the trick :).↵
↵
this is present in a lot (really a a lot) of atcoder beginner contest E,F problems and really popular but rarely taught anywhere.↵
↵
<spoiler summary="c++">↵
```↵
#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]);↵
}↵
```↵
</spoiler>↵
↵
↵
</spoiler>↵
↵
8.DP bitmask↵
------------------↵
↵
here a bitmask is chosen to identify if an element is used or not , we may use this in a lot of ways , i remember using a bitmask of $3^n$ or even $4^n$ but let's focus now on $2^n$↵
↵
let's solve this problem [Matching](https://atcoder.jp/contests/dp/tasks/dp_o).↵
↵
<spoiler summary="the state">↵
dp[current guy][bitmask of choosen girls]=dp[21][1<<21]↵
</spoiler>↵
↵
<spoiler summary="the transition">↵
for each girl try to match it with the current guy if possible (the girl was not chosen and they are compatible).↵
</spoiler>↵
↵
<spoiler summary="the code">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll int64_t↵
#define ld long double↵
const int N=100010,M=1e9+7;↵
ll mem[21][1<<21];↵
int vis[21][1<<21];↵
ll n;↵
bool comp[21][21];↵
ll dp(int i,int m){↵
if(i==n)return 1;↵
if(vis[i][m])return mem[i][m];↵
vis[i][m]=1;↵
ll &res=mem[i][m];↵
for(int j=0;j<n;j++){↵
if((m>>j)&1)continue;↵
if(!comp[i][j])continue;↵
res+=dp(i+1,m|(1<<j));↵
}↵
res%=M;↵
return res;↵
}↵
signed main(){↵
cin>>n;↵
for(int i=0;i<n;i++){↵
for(int j=0;j<n;j++)cin>>comp[i][j];↵
}↵
cout<<dp(0,0);↵
↵
}↵
```↵
</spoiler>↵
↵
what is the time complexity of this code?↵
↵
<spoiler summary="the answer">↵
do not mistake the mistake of $n^22^n$↵
the time complexity in worst case (where the whole array is ones) is:↵
$$↵
\sum_{j=0}^{n-1} n\binom{n}{j}↵
$$↵
which in worst case $n=21$ would be $44039730$↵
</spoiler>↵
↵
↵
9.DP on tree↵
------------------↵
↵
the most annoying kind especially with re rooting , lets focus on the main idea.↵
↵
in this kind of dp you must chose a root and calculate the result of each node depending on its children.↵
↵
like in the [Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p) problem.↵
↵
the state of the dp is $dp[node][color]$ so if the current color is black you consider the answer of $dp[child][white]$ , otherwise you consider both $dp[child][white]$ and $dp[child][black]$↵
↵
note that we must multiply the childrens answer (not add)↵
↵
<spoiler summary="c++">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll int64_t↵
#define ld long double↵
#define pb push_back↵
const int N=100010,M=1e9+7;↵
ll n;↵
vector<int> adj[N];↵
bool vis[N][2];↵
ll mem[N][2];↵
ll dp(int i,int d,int c){↵
if(vis[i][c])return mem[i][c];↵
vis[i][c]=1;↵
ll &res=mem[i][c];↵
res=1;↵
int cn=0;↵
for(int j:adj[i]){↵
if(j==d)continue;↵
cn++;↵
if(c==0){//it is white↵
res*=(dp(j,i,1)+dp(j,i,0));↵
}else{↵
res*=dp(j,i,0);↵
}↵
res%=M;↵
}↵
return res;↵
}↵
signed main(){↵
cin>>n;↵
for(int i=1,x,y;i<n;i++){↵
cin>>x>>y;↵
adj[x].pb(y);↵
adj[y].pb(x);↵
}↵
cout<<(dp(1,1,0)+dp(1,1,1))%M;↵
}↵
```↵
</spoiler>↵
↵
10.DP with segment tree↵
------------------↵
↵
this kind of DP is almost always deduced as we only need to know segment trees so solve this.↵
↵
some times we only need to find minimum or maximum in range to solve them .↵
↵
a good example would be [Flowers](https://atcoder.jp/contests/dp/tasks/dp_q)↵
↵
in this problem we must chose an increasing sub sequence of heights such that the sum of values as maximum ↵
↵
we can solve it for each index from $1$ to $n$ get the maximum answer among all heights that are less than $h(i)$ and add the value of the current flower to it and then update this value in the segment tree.↵
↵
the solution is left to the reader :).↵
↵
11. DP with matrices↵
------------------↵
↵
if you do know matrices you really should not be reading this as all matrices problems are DP in fact, but you might have fun solving [Walk](https://atcoder.jp/contests/dp/tasks/dp_r)↵
↵
Note that i might make a tutorial about matrices some day! stay tuned :).↵
↵
↵
12.digit DP↵
------------------↵
↵
this is one of the most annoying because if you made a mistake debugging is impossible.↵
↵
problems of digit DP give you two numbers a,b such that their values are really huge (up to $10^{100000}$) and ask you to count how many numbers between them satisfies something.↵
↵
in the problem [Digit Sum](https://atcoder.jp/contests/dp/tasks/dp_s).↵
↵
this is a not really easy problem , and the state is more annoying↵
↵
↵
<spoiler summary="the state">↵
$dp$[index][are we sure we are greater than a?][are we sure we are less than b?][mod on D]=$dp[N][2][2][100]$↵
we can just imagine filling digits in our current value.↵
</spoiler>↵
↵
<spoiler summary="the transition">↵
in the transition we add an integer digit , but what can we add?↵
traversing the digits from left to right (bigger values) because the decide what we can do later↵
using this code:↵
↵
```↵
if(we are sure we are greater than a)L=0;↵
else↵
L=a[i]-'0'↵
if(we are sure we are less than b)R=9;↵
else R=b[i]-'0';↵
```↵
</spoiler>↵
↵
so our solution is:↵
↵
<spoiler summary="c++">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define ll int64_t↵
#define ld long double↵
#define pb push_back↵
const int N=10010,M=1e9+7;↵
string a,b;↵
ll D;↵
ll mem[N][2][2][100];↵
int vis[N][2][2][100];↵
ll dp(int i,int bl,int br,int md){↵
if(i==a.size())return md==0;↵
if(vis[i][bl][br][md])return mem[i][bl][br][md];↵
vis[i][bl][br][md]=1;↵
ll &res=mem[i][bl][br][md];↵
int L=a[i]-'0',R=b[i]-'0';↵
if(bl)L=0;↵
if(br)R=9;↵
for(int j=L;j<=R;j++){↵
res+=dp(i+1,bl|(j>L),br|(j<R),(md+j)%D);↵
}↵
res%=M;↵
return res;↵
}↵
↵
signed main(){↵
cin>>b;↵
a=string(b.size()-1,'0')+"1";↵
cin>>D;↵
cout<<dp(0,0,0,0);↵
}↵
```↵
</spoiler>↵
↵
and i think that's it as much as i would like to solve more , but i think i will leave it to you to view more and more dp problems , thank you for reading :).↵
↵
