Is there some trick to convert DFS+memo into dp

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

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

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

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

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 :)

Comments (8)

Show archived | Write comment?

Evro

4 years ago, # |

Generally Speaking? No, I haven't found any proven systematic method to convert a Recursive approach to Iterative approach.

Technically Speaking? Yeah, There's plenty of insights the recursive solution gives you,

For example

1-You're able to find what values to return in the base cases, and what are the base cases themselves.

2-You're able to find if you need to iterate from 0 -> n or n -> 0, depending on what is calculated in the base case

3-You're able to find the transition between states. As they're the Recursive calls

dp[i][tg][tp]=(solve(i+1,tg-gp[i],tp+pf[i])+solve(i+1,tg,tp))%MOD;

Means $$$dp[i][tg][tp] = dp[i+1][tg - gp[i]][tp + pf[i]] + dp[i+1][tg][tp]$$$

Sometimes those are enough to write an iterative solution, sometimes not. You just need to practice understanding what does the dp array mean, like what does dp[i][tg][tp] means here, Once you're able to grasp the physical meaning of a dp state, You're probably able to discover the transitions and the base cases without writing recursive solutions.

→ Reply

DeadlyCritic

I guess you can(in some cases) store all the states(push_back them to an array when the dfs $$$ends$$$, and mark each state using boolean array or a bitset), so? i don't think if it helps with memory, but is indeed an iterative way to think about it :).

retr0coderxyz

4 years ago, # ^ |

Well I tried once but it was just messy. Atleast I couldnt code it properly. I wanna learn that table method. Lets see. Thanks for the help!

Implementation using arrays


vector<int> order;

void dfs(int now){
    mark[now] = 1;
    for(u in all the states we need to know to calculate dp[now]){
        if(!mark[u])dfs(u)
    }
    order.push_back(now);
}

int main(){
    //we want to calculate dp[1];
    dfs(1);
    for(u in order){//from beginning to end
        //calculate dp[u]
        ...
    }
    cout << dp[1];
}

Implementation using map


vector<T> order;//T is any type, like integer or pair or anything else
map<T, int> dp;//T is the same
map<T, bool> mark;

dfs(T now){
    mark[now] = 1;
    for(u in all the states we need to know to calculate dp[now]){
        if(!mark.count(u)){//use this to check if u is marked or not
            dfs(u);
        }
    }
    order.push_back(now);
}


int main(){
    //we want to calculate dp[1]
    dfs(1);
    for(u in order){//from beginning to end
        //calculate dp[u]
    }
    cout << dp[1];
}

navneet.h

one thing you could do is maintain vector or stack, maintaining some struct binding of required variables, and visited branch, for example if you have gone through the child of particular parent, you should maintain a pointer pointing which child had already been visited, so you could directly start from that. this method is not that memory efficient but still very faster, as you are avoiding system stack which was used by recursion.

Still that would be bad right?

code for iterative postorder traversal of binary tree


struct Data{
    TreeNode * ref;
    bool left_visited,right_visited;
    Data(TreeNode *obb, bool lf, bool rg) :ref(obb), left_visited(lf), right_visited(rg){}
};
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if(!root) return ans;
        stack<Data> st;
        st.push(Data(root,false,false));
        while(!st.empty()){
            auto &tp = st.top();
            if(tp.ref->left and !tp.left_visited){
                Data lft = Data(tp.ref->left,false,false);
                st.push(lft);
                tp.left_visited = true;
                continue;
            }
            if(tp.ref->right and !tp.right_visited){
                Data rgt = Data(tp.ref->right,false,false);
                st.push(rgt);
                tp.right_visited = true;
                continue;
            }
            ans.emplace_back(tp.ref->val);
            st.pop();   
        }
        return ans;
    }
};

This is my code for iterative postorder traversal of binary traversal it is 100 percent faster than other submissions also 100 percent memory efficient in leetcode. When I am free I will post the iterative version of your dp.

SuperJ6

Often you can sort by dfs order then just do iterative dp from there. Still requires a dfs though.

retr0coderxyz's blog