DP with pair<int,int> and rebuild answer backwards


  • 0
    L

    Same idea as https://discuss.leetcode.com/topic/49441/easy-dp-with-path-record-c-code-o-n-2-time-on-worst-case-o-n-space the improvement is to get rid of the "go to".

    The key is sort array first, then put element into next bucket as soon as it could mod an element in current bucket.
    The trick is use pair to store information for future rebuild answer. pair->first: value, pair->second: index of pair in previous bucket which current value could mod to 0, so we could trace from first element of last bucket back to beginning.

    see this case [1,2,3,4,5,6,7,24]
    
    at last it runs like this:
    
     1 | 2 | 4 | 24
       | 3 | 6 |
       | 5 |    
       | 7 |    
    
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        	if (nums.empty()){
        		return vector<int>();
        	}
        
        	sort(nums.begin(), nums.end());
        	int n = nums.size(), maxLenth = 0;
        	// pair : first -> current index, second -> pre index
        	vector<vector<pair<int, int>>> dp(n, vector<pair<int, int>>());
        
        	for (int i = 0; i < n; i++){
        		int k = maxLenth;
        		bool find = false;
        		for (int j = k - 1; j >= 0 && !find; j--){
        			for (int t = 0; t < dp[j].size() && !find; t++){
        				if (nums[i] % dp[j][t].first == 0){
        					dp[j + 1].emplace_back(nums[i], t);
        					maxLenth = max(maxLenth, j + 2);
        					find = true;
        				}
        			}
        		}
        
        		if (!find){
        			dp[0].emplace_back(nums[i], -1);
        			maxLenth = max(maxLenth, 1);
        		}
        	}
        
        	vector<int> res;
        	int i = maxLenth - 1, index = 0;
        	while (i >= 0){
        		res.insert(res.begin(), dp[i][index].first);
        		index = dp[i][index].second;
        		i--;
        	}
        
        	return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.