DP Bottom-Up


  • 0
    M

    With this question, since the target is <= 15 characters then worst case we will use 15 stickers to solve the problem. We can model the solution recursively as F(i, n) where n denotes how many words we are considering (0 <= n <= 15) and where i denotes the maximum amount of letters taken from target when using the i'th word as the last word in our solution so far. One can think of n as how many edges away from the initial state are we when considering the problem as a graph.

    Thus:

    F(i, n) = max{
        // considering all solutions of the form:
        // ..., sticker[j], sticker[i]
        for j = 0 to stickers.size() - 1:
            F(j, n - 1)
    }
    

    If at any point F(i, n) uses all letters in our target word, we can stop as we have found a solution early. The base case is obviously F(i, 0) = target for all i, as we would not affect the target when considering no words.

    Now to actually code this recurrence, we should store the current amount of letters (letter -> count map) in the target as opposed to a number. This is so we can compute how many letters a particular word removes from any solution (sub-problem).

    int minStickers(vector<string>& stickers, string target) {
            vector<vector<int>> letters(stickers.size(), vector<int>(26));
            for(int i = 0; i < stickers.size(); ++i) {
               for(auto ch : stickers[i]) {
                   letters[i][ch - 'a']++;
               }
            }
    
            vector<int> target_letters(26);
            for(char ch : target) target_letters[ch - 'a']++;
            vector<vector<int>> dp(stickers.size());
    
            for(int i = 0; i < stickers.size(); ++i) {
                dp[i] = target_letters;
            }
            
            for(int i = 1; i <= 15; ++i) {
                vector<vector<int>> next;
                for(int j = 0; j < stickers.size(); ++j) {
                    int best = INT_MAX;
                    vector<int> bestResidual;
                    
                    for(int k = 0; k < dp.size(); ++k) {
                        vector<int> curr = dp[k];
                        for(int i = 0; i < curr.size(); ++i) {
                            curr[i] -= min(curr[i], letters[j][i]);
                        }
                        
                        int size = accumulate(curr.begin(), curr.end(), 0);
                        if(size <= best) {
                            best = size;
                            bestResidual = curr;
                        }
                        
                        if(size == 0) return i;
                    }
                    
                    next.push_back(bestResidual);
                }
                
                swap(next, dp);
            }
            
            return -1;
        }
    

Log in to reply
 

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