Form Largest Integer With Digits That Add up to Target LeetCode solution in C++

1
class Solution {
2
 public:
3
  vector<vector<string>> dp;
4
  string largestNumber(vector<int> &cost, int target) {
5
    dp.resize(10, vector<string>(target + 1, "-1"));
6
    return solve(cost, 0, target);
7
  }
8

9
  string solve(vector<int> &cost, int idx, int target) {
10
    if (!target) return "";
11
    if (target < 0 || idx >= size(cost)) return "0";
12

13
    if (dp[idx][target] != "-1") return dp[idx][target];
14

15
    string a = to_string(idx + 1) + solve(cost, 0, target - cost[idx]);
16
    string b = solve(cost, idx + 1, target);
17

18
    return dp[idx][target] = a.back() == '0'      ? b
19
                             : b.back() == '0'    ? a
20
                             : size(a) == size(b) ? max(a, b)
21
                             : size(a) > size(b)  ? a
22
                                                  : b;
23
  }
24
};