How To Convert Recursive Code to Tabulation
Let's take the Unique Paths problem for an example.(please read the problem before reading this blog)
recursive code
int n,m;
int dp[101][101];
int solve(int i,int j){
if(i==n-1&&j==m-1){ //base case
return 1;
}
if(dp[i][j]!=-1)return dp[i][j]; //memoization
int ans=0;
if(i+1<n){
ans+=solve(i+1,j); //move down
}
if(j+1<m){
ans+=solve(i,j+1); //move right
}
return dp[i][j]=ans;
}
int main(){
cin>>n>>m;
memset(dp,-1,sizeof(dp));
cout<<solve(0,0)<<endl; //0,0 initial position
return 0;
}
tabulation is a bottom up approach so for i we need to calculate i+1 first and same for j
for this problem the tabulation loops will look like this
for(int i=n-1;i>-1;i--){
for(int j=m-1;j>-1;j--){
}
}
Note
-The loops should cover all valid states.
-Every loop represents one state so if we have 3 states then we have to make 3 loops.
-If the transition was from i to i-1 then the loop will be for(int i=0;i<=n-1;i++)
step1 replace base condition to
if(i==n-1&&j==m-1){
dp[i][j]=1;
continue; //if there is any early return statement in recursive code replace return with continue
}
step2 remove this line
if(dp[i][j]!=-1)return dp[i][j];
step3 replace following lines
//recursive //tabulation
int ans=0; int ans=0;
if(i+1<n){ if(i+1<n){
ans+=solve(i+1,j); ans+=dp[i+1][j];
} ---------> }
if(j+1<m){ if(j+1<m){
ans+=solve(i,j+1); ans+=dp[i][j+1];
} }
return dp[i][j]=ans; dp[i][j]=ans;
Final Code
int main(){
cin>>n>>m;
vector<vector<int>>dp(101,vector<int>(101,0));
for(int i=n-1;i>-1;i--){
for(int j=m-1;j>-1;j--){
if(i==n-1&&j==m-1){
dp[i][j]=1;
continue;
}
int ans=0;
if(i+1<n){
ans+=dp[i+1][j];
}
if(j+1<m){
ans+=dp[i][j+1];
}
dp[i][j]=ans;
}
}
cout<<dp[0][0]<<endl;
return 0;
}
you can convert almost every recursive code to tabulation by replacing few lines like this after doing few problems you will be able to directly write tabulation code
Now let's try to optimize space.
Space Optimization
in this problem we can see the ith state is depending on ith and i+1 state so there is no use of i+2,i+3 ... we can simply use two arrays one for ith state and one for i+1
vector<vector<int>>dp(2,vector<int>(101,0));//dp[0] for current value of i and dp[1] for i+1
//or
vector<int>curr(101,0);
vector<int>next(101,0);
Note
-We can not do space optimization in dp path printing problems.
-We will use 2d array method but you can replace it with 2 arrays if you like.
-we can apply space optimization in most array dp problem where there is index->index+1 transition
step 1
replace dp[i][j] to dp[0][j] and dp[i+1][j] to dp[1][j]
step 2
add swap(dp[0],dp[1]) or dp[1]=dp[0] after we have computed all value of dp[0]
Final Code
int main(){
cin>>n>>m;
vector<vector<int>>dp(2,vector<int>(101,0));
for(int i=n-1;i>-1;i--){
for(int j=m-1;j>-1;j--){
if(i==n-1&&j==m-1){
dp[0][j]=1; //dp[i][j]->dp[0][j]
continue;
}
int ans=0;
if(i+1<n){
ans+=dp[1][j]; //dp[i+1][j]->dp[1][j]
}
if(j+1<m){
ans+=dp[0][j+1]; //dp[i][j+1]->dp[0][j+1]
}
dp[0][j]=ans; //dp[i][j]->dp[0][j]
}
swap(dp[0],dp[1]);// or you can also use dp[1]=dp[0] but not recommended due to additional copy operations
}
cout<<dp[1][0]<<endl; //because we swapped dp our final answer will be in dp[1] state
return 0;
}
practice problem:
https://cses.fi/problemset/task/1636
Range transition optimization
let's modify this problem
now if the robot is in grid[i][j] he can move to grid[i][j+1] or grid[i+1][x] ( x ∈ [j, m-1] )
we will have to return answer modulo 1e9+7 but for readability i am not adding mod in the code
code without optimization O(n*m*m)
int n,m;
int main(int T){
cin>>n>>m;
vector<vector<int>>dp(2,vector<int>(101,0));
for(int i=n-1;i>-1;i--){
for(int j=m-1;j>-1;j--){
if(i==n-1&&j==m-1){
dp[0][j]=1;
continue;
}
int ans=0;
if(i+1<n){
for(int t=j;t<m;t++){ //range transition
ans+=dp[1][t];
}
}
if(j+1<m){
ans+=dp[0][j+1];
}
dp[0][j]=ans;
}
swap(dp[0],dp[1]);
}
cout<<dp[1][0]<<endl;
return 0;
}
We are doing range transition in i+1 position to optimize this we can apply prefix sum to our code after calculation of ith dp vector we will apply prefix sum to it then swap dp[0] and dp[1] so the prefix sum dp will become i+1 state
code with prefix sum optimization O(n*m)
int n,m;
int main(int T){
cin>>n>>m;
vector<vector<int>>dp(2,vector<int>(101,0));
for(int i=n-1;i>-1;i--){
for(int j=m-1;j>-1;j--){
if(i==n-1&&j==m-1){
dp[0][j]=1;
continue;
}
int ans=0;
if(i+1<n){
ans+=dp[1][m-1]-((j==0)?0:dp[1][j-1]); // sum of m-1 to j -> pre[m-1]-pre[j-1]
}
if(j+1<m){
ans+=dp[0][j+1];
}
dp[0][j]=ans;
}
for(int j=1;j<m;j++){
dp[0][j]+=dp[0][j-1]; // applying prefix sum after computing the full row
}
swap(dp[0],dp[1]);
}
cout<<dp[1][0]<<endl;
return 0;
}
practice problem:
https://mirror.codeforces.com/contest/2091/problem/F
depending on problem we can apply segment tree similarly to make range transition efficient or find range min max etc.
If you know any good prefix sum DP or space optimization problems, feel free to share I’d love to add them to the blog.
Comments (0)
