# DP Bottom-Up

• 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;
}
``````

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