Backtracking v/s Memoization in Dynamic Programming
Dark Nite
187

Check out this generic solution for - Campus Bikes II. The question I want to asks follows after the code.

class Solution {
    
    int dfs (vector<vector<int>> *w, vector<vector<int>> *b, int wi, int state, vector<int>* dp) {
                
        if (wi==(*w).size()) return 0;
        
        if ((*dp)[state]!=0) return (*dp) [state];
        int mindis = INT_MAX;
                
        for (int i=0; i<(*b).size(); i++) {
            
            if ((state & (1<<i))==0) {
                
                mindis = min (
                              mindis, 
                              abs ( (*w)[wi][0]-(*b)[i][0] ) + 
                              abs ( (*w)[wi][1]-(*b)[i][1] ) + 
                              dfs (w, b, wi+1, (state | (1<<i)), dp)
                             );
                
            }
            
        }
        
        (*dp)[state]=mindis;
        cout << "returning for state " << state << " " << mindis << endl;
        return mindis;
    }
    
public:
    int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
        
        int n=bikes.size();
        vector<int> dp ((1<<n), 0) ;
        
        return dfs( &workers, &bikes, 0, 0, &dp);
        
    }
};

In the above solution memoization has been used due to dp.

I would like to modify the question to Not only finding the minimum sum of distances the workers have to travel but also to get which worker was alloted which bike. Is it possible to do this without sacrificing on memoization ? If yes, can you please explain how ?

Comments (0)