LeetCode 1449. Form Largest Integer With Digits That Add up to Target

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<int> f(target + 1, INT_MIN);
        f[0] = 0;
        for (auto c : cost)
            for (auto j = c; j <= target; ++j)
                f[j] = max(f[j], f[j - c] + 1);
        if (f[target] < 0) return "0";
        string ans;
        for (int i = 8, j = target; i >= 0; --i)
            for (int c = cost[i]; j >= c && f[j] == f[j - c] + 1; j -= c)
                ans += '1' + i;
        return ans;
    }
};