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 "997", 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 == 91 <= cost[i] <= 50001 <= target <= 5000
Solution: DP
dp(target) := largest number to print with cost == target.
dp(target) = max(dp(target – d) + cost[d])
Time complexity: O(target^2)
Space complexity: O(target^2)
C++ / Top Down
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 280 ms class Solution { public: string largestNumber(vector<int>& cost, int target) { vector<string> cache(target + 1); // dp[i] := largestNumber that has cost i. function<string(int)> dp = [&](int t) -> string { if (t < 0) return "0"; // Invalid. if (t == 0) return ""; // Found a solution. if (!cache[t].empty()) return cache[t]; cache[t] = "0"; // Important !!! for (int d = 1; d <= 9; ++d) { const string& cur = dp(t - cost[d - 1]); if (cur != "0" && cur.length() + 1 >= cache[t].length()) cache[t] = to_string(d) + cur; } return cache[t]; }; return dp(target); } }; |
C++ / Bottom Up
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 240 ms class Solution { public: string largestNumber(vector<int>& cost, int target) { // dp[i] := largestNumber that has cost i. vector<string> dp(target + 1, "0"); dp[0] = ""; for (int t = 1; t <= target; ++t) for (int d = 1; d <= 9; ++d) { const int s = t - cost[d - 1]; if (s < 0 || dp[s] == "0" || dp[s].length() + 1 < dp[t].length()) continue; dp[t] = to_string(d) + dp[s]; } return dp[target]; } }; |
To avoid string copying, we can store digit added (in order to back track the parent) and length of the optimal string.
Time complexity: O(target)
Space complexity: O(target)
C++ / O(target)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// Author: Huahua, 25 ms class Solution { public: string largestNumber(vector<int>& cost, int target) { vector<pair<int, int>> cache(target + 1, {-1, -1}); // dp[i] := {digit, length} of largestNumber that has cost i. function<pair<int, int>(int)> dp = [&](int t) -> pair<int, int> { if (t < 0) return {0, -1}; // Invalid. if (t == 0) return {0, 0}; // Found a solution. if (cache[t].first != -1) return cache[t]; cache[t] = {0, -1}; // make as solved but invalid. for (int d = 1; d <= 9; ++d) { const int l = dp(t - cost[d - 1]).second; if (l != -1 && l + 1 >= cache[t].second) cache[t] = {d, l + 1}; } return cache[t]; }; dp(target); if (cache[target].second <= 0) return "0"; string ans; while (target) { ans += cache[target].first + '0'; target -= cost[cache[target].first - 1]; } return ans; } }; |
C++ / O(target)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 28 ms class Solution { public: string largestNumber(vector<int>& cost, int target) { // dp[i] = {d, length} of the largest number that costs i. vector<pair<int, int>> dp(target + 1, {-1, -1}); dp[0] = {0, 0}; for (int t = 1; t <= target; ++t) for (int d = 1; d <= 9; ++d) { const int s = t - cost[d - 1]; if (s < 0 || dp[s].second == -1 || dp[s].second + 1 < dp[t].second) continue; dp[t] = {d, dp[s].second + 1}; } if (dp[target].second == -1) return "0"; string ans; while (target) { ans += dp[target].first + '0'; target -= cost[dp[target].first - 1]; } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment