Hello guys,↵
↵
I have been trying to solve Dp problems. When I read a problem I try to translate it into DFS(recursion) which ends up having TLE, then I simply store the state variables so it passes the time limit. But What I want to learn is that, any trick is there to convert this into iterative DP( As I guess DFS+memo has large constant factor).↵
↵
For example take this problem: [link](https://leetcode.com/problems/profitable-schemes/)↵
↵
<spoiler summary="TLE Code non memoized">↵
↵
~~~~~↵
const int MOD=(1e9+7);↵
class Solution {↵
vector<int> gp,pf;↵
int g,p;↵
int n;↵
public:↵
long long solve(int i,int tg,int tp)↵
{↵
if(tg<0)return 0;↵
↵
if(i>=n && tp>=p)return 1;↵
if(i>=n)return 0;↵
↵
return (solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;↵
}↵
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {↵
gp=group;↵
pf=profit;↵
g=G;↵
p=P;↵
n=group.size();↵
↵
long long ans=solve(0,G,0);↵
return ans%MOD;↵
}↵
};↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="DFS+Memo Passed">↵
↵
~~~~~↵
const int MOD=(1e9+7);↵
class Solution {↵
vector<int> gp,pf;↵
int g,p;↵
int n;↵
int dp[101][101][1000];↵
public:↵
long long solve(int i,int tg,int tp)↵
{↵
if(tg<0)return 0;↵
↵
if(i>=n && tp>=p)return 1;↵
if(i>=n)return 0;↵
if(dp[i][tg][tp]!=-1)return dp[i][tg][tp];↵
return dp[i][tg][tp]=(solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;↵
}↵
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {↵
gp=group;↵
pf=profit;↵
g=G;↵
p=P;↵
n=group.size();↵
memset(dp,-1,sizeof(dp));↵
long long ans=solve(0,G,0);↵
return ans%MOD;↵
}↵
};↵
~~~~~↵
↵
</spoiler>↵
↵
↵
So I want to learn a generic technique ( not limited to this problem) to write iterative solutions as No matter how hard I try ↵
I am unable to grasp iterative writing method. It would be great if you guys could help me in this. Thank you!↵
↵
↵
**P.S. Please Dont downvote this blog guys as some people have extension to hide bad blogs. Once I get an answer you can downvote it to your hearts content. Thanks :)**
↵
I have been trying to solve Dp problems. When I read a problem I try to translate it into DFS(recursion) which ends up having TLE, then I simply store the state variables so it passes the time limit. But What I want to learn is that, any trick is there to convert this into iterative DP( As I guess DFS+memo has large constant factor).↵
↵
For example take this problem: [link](https://leetcode.com/problems/profitable-schemes/)↵
↵
<spoiler summary="TLE Code non memoized">↵
↵
~~~~~↵
const int MOD=(1e9+7);↵
class Solution {↵
vector<int> gp,pf;↵
int g,p;↵
int n;↵
public:↵
long long solve(int i,int tg,int tp)↵
{↵
if(tg<0)return 0;↵
↵
if(i>=n && tp>=p)return 1;↵
if(i>=n)return 0;↵
↵
return (solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;↵
}↵
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {↵
gp=group;↵
pf=profit;↵
g=G;↵
p=P;↵
n=group.size();↵
↵
long long ans=solve(0,G,0);↵
return ans%MOD;↵
}↵
};↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="DFS+Memo Passed">↵
↵
~~~~~↵
const int MOD=(1e9+7);↵
class Solution {↵
vector<int> gp,pf;↵
int g,p;↵
int n;↵
int dp[101][101][1000];↵
public:↵
long long solve(int i,int tg,int tp)↵
{↵
if(tg<0)return 0;↵
↵
if(i>=n && tp>=p)return 1;↵
if(i>=n)return 0;↵
if(dp[i][tg][tp]!=-1)return dp[i][tg][tp];↵
return dp[i][tg][tp]=(solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;↵
}↵
int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) {↵
gp=group;↵
pf=profit;↵
g=G;↵
p=P;↵
n=group.size();↵
memset(dp,-1,sizeof(dp));↵
long long ans=solve(0,G,0);↵
return ans%MOD;↵
}↵
};↵
~~~~~↵
↵
</spoiler>↵
↵
↵
So I want to learn a generic technique ( not limited to this problem) to write iterative solutions as No matter how hard I try ↵
I am unable to grasp iterative writing method. It would be great if you guys could help me in this. Thank you!↵
↵
↵
**P.S. Please Dont downvote this blog guys as some people have extension to hide bad blogs. Once I get an answer you can downvote it to your hearts content. Thanks :)**
