1449. Form Largest Integer With Digits That Add up to Target ------------H ~~~~

 Given an array of integers cost and an integer target. Return the maximum integer you can paint under the following rules:

• The cost of painting a digit (i+1) is given by cost[i] (0 indexed).
• The total cost used must be equal to target.
• Integer does not have digits 0.

Since the answer may be too large, return it as string.

If there is no way to paint any integer given the condition, return "0".

 

Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation:  The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" is the largest number.
Digit    cost
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.

Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It's not possible to paint any integer with total cost equal to target.

Example 4:

Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

 

Constraints:

• cost.length == 9
• 1 <= cost[i] <= 5000
• 1 <= target <= 5000

A:

递归， 每次优先抽取一个最小cost，（同时index最大）。然后use memorization。

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        // sort the values by value.
        vector<int> copy(cost);
        sort(copy.begin(), copy.end());
        vector<int> A;
        for (int i = 0; i < copy.size(); i++) {// contains non-duplicated values
            if (i == 0 || copy[i] != copy[i - 1])
                A.push_back(copy[i]);
        }
        unordered_map<int, int> cost2number;
        for (int i = 0; i < cost.size(); i++) {
            cost2number[cost[i]] = i + 1;   // record only the larget value with same cost
        }
        unordered_map<int, string> resultMap;
        return helper(A, cost2number, target, resultMap);
    }
private:
    string helper(vector<int>& A, unordered_map<int, int>& cost2number, int target, unordered_map<int, string> &resultMap) {
        if (target == 0)
            return "";
        if (target < 0)
            return "0";
        auto iter = resultMap.find(target);
        if (iter != resultMap.end())
            return resultMap[target];
        int maxSubLen = -1;
        vector<string> subresult;
        vector<int> usedCost;
        for (int i = 0; i < A.size(); i++) {
            string subRes = helper(A, cost2number, target - A[i],resultMap);
            if (subRes == "0")
                continue;
            if (maxSubLen < 0 || subRes.length() >= maxSubLen) {
                usedCost.push_back(A[i]);
                subresult.push_back(subRes);
                maxSubLen = subRes.length();
            }
        }
        // now all subresult are of the same length;, find the max index
        int maxCostUsed = 0;
        int maxFirstNumber = 0;
        for (int i = 0; i < usedCost.size(); i++) {
            if (subresult[i].length() != maxSubLen)  // skip those with shorter length
                continue;

            if (maxFirstNumber < cost2number[usedCost[i]]) {
                maxCostUsed = i;
                maxFirstNumber = cost2number[usedCost[i]];
            }
        }
        if (subresult.empty())
            return "0";
        string res = to_string(maxFirstNumber) + subresult[maxCostUsed];
        resultMap[target] = res;
        return res;
    }
};

***************然而，上面的解法    LTE    ********

我的一个考量是，更小的target ,其返回的string result can be longer。(???????)因此，不能因为跳过小的target. -----------------嗯，我的考虑是对的。

更改了另一个地方，就是：helper() 的最后。  如果 target 返回的是"0"的时候，也把map[target] = "0"

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        // sort the values by value.
        vector<int> copy(cost);
        sort(copy.begin(), copy.end());
        vector<int> A;
        for (int i = 0; i < copy.size(); i++) {// contains non-duplicated values
            if (i == 0 || copy[i] != copy[i - 1])
                A.push_back(copy[i]);
        }
        unordered_map<int, int> cost2number;
        for (int i = 0; i < cost.size(); i++) {
            cost2number[cost[i]] = i + 1;   // record only the larget value with same cost
        }
        unordered_map<int, string> resultMap;
        return helper(A, cost2number, target, resultMap);
    }
private:
    string helper(vector<int>& A, unordered_map<int, int>& cost2number, int target, unordered_map<int, string> &resultMap) {
        if (target == 0)
            return "";
        if (target < 0)
            return "0";
        auto iter = resultMap.find(target);
        if (iter != resultMap.end())
            return resultMap[target];
        int maxSubLen = -1;
        vector<string> subresult;
        vector<int> usedCost;
        for (int i = 0; i < A.size(); i++) {
            string subRes = helper(A, cost2number, target - A[i],resultMap);
            if (subRes == "0")
                continue;
            if (maxSubLen < 0 || subRes.length() >= maxSubLen) {
                usedCost.push_back(A[i]);
                subresult.push_back(subRes);
                maxSubLen = subRes.length();
            }
        }
        // now all subresult are of the same length;, find the max index
        int maxCostUsed = 0;
        int maxFirstNumber = 0;
        for (int i = 0; i < usedCost.size(); i++) {
            if (subresult[i].length() != maxSubLen)  // skip those with shorter length
                continue;

            if (maxFirstNumber < cost2number[usedCost[i]]) {
                maxCostUsed = i;
                maxFirstNumber = cost2number[usedCost[i]];
            }
        }
        string res = "0";
        if ( not subresult.empty())
            res = to_string(maxFirstNumber) + subresult[maxCostUsed];
        
        resultMap[target] = res;            
        return res;
    }
};

 ********************下一次，不用递归 memorization,  转而用 正向 DP *******一个个前进