Is there some trick to convert DFS+memo into dp

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

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

5 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

5 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