Is there some trick to convert DFS+memo into dp

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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 :)

Комментарии (8)

Показать архивные | Написать комментарий?

Evro

4 года назад, # |

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.

→ Ответить

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 года назад, # ^ |

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