# C++ DP solution with explanation

• ``````// So the idea here is copied from the rest of the solutions:
// DP[target_string] = MIN_For_All_Stickers(1 + DP[string_without_sticker_applied])
// Then the tricky thing is to solve the sub-problem here, how do we even
// represent the sub problem.
// 1) We can have a mask to represent which characters in the target string are still pending.
//   example target: "Test", initially the mask will be 15 (1111), i.e. all strings have to be matched.
//   Then once lets say 'e' gets matched, we are left with "T_st" and mask will be 11 (1011).
//   and so on...Base case will be mask = 0, where solution will be 0.
// 2) To represent the sub problems we can also use actual strings around, i.e. "test", "tst" etc.
//    A good solution had these in the sorted way, i.e "estt" and "stt", etc.
int helper(vector<string>& stickers, string& target, unordered_map<int, int>& cache, int mask) {
if (!mask) { return 0; } // If mask == 0, return 0;

if (it != cache.end()) {
return (*it).second;
}

int N = target.size();
int result = INT_MAX;
for (string s : stickers) {
for (char c : s) {
for (int i=0; i < N; ++i) {
// Check if a character in sticker matches a not-yet matched char in target.
if (target[i] == c && ((new_mask >> (N - i - 1)) & 1)) {
break; // This is important, otherwise one character can be matched to many in target.
}
}
}
int sub_problem_result = helper(stickers, target, cache, new_mask);
if (sub_problem_result == -1) { cache[mask] = -1; return -1; }

result = min(result, 1 + sub_problem_result);
}
}
cache[mask] = result == INT_MAX ? -1 : result;