Description#
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. - The integer does not have
0 digits.
Since the answer may be very large, return it as a 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 is impossible to paint any integer with total cost equal to target.
Constraints:
cost.length == 91 <= cost[i], target <= 5000
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution:
def largestNumber(self, cost: List[int], target: int) -> str:
f = [[-inf] * (target + 1) for _ in range(10)]
f[0][0] = 0
g = [[0] * (target + 1) for _ in range(10)]
for i, c in enumerate(cost, 1):
for j in range(target + 1):
if j < c or f[i][j - c] + 1 < f[i - 1][j]:
f[i][j] = f[i - 1][j]
g[i][j] = j
else:
f[i][j] = f[i][j - c] + 1
g[i][j] = j - c
if f[9][target] < 0:
return "0"
ans = []
i, j = 9, target
while i:
if j == g[i][j]:
i -= 1
else:
ans.append(str(i))
j = g[i][j]
return "".join(ans)
|
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
29
30
31
32
33
34
35
36
| class Solution {
public String largestNumber(int[] cost, int target) {
final int inf = 1 << 30;
int[][] f = new int[10][target + 1];
int[][] g = new int[10][target + 1];
for (var e : f) {
Arrays.fill(e, -inf);
}
f[0][0] = 0;
for (int i = 1; i <= 9; ++i) {
int c = cost[i - 1];
for (int j = 0; j <= target; ++j) {
if (j < c || f[i][j - c] + 1 < f[i - 1][j]) {
f[i][j] = f[i - 1][j];
g[i][j] = j;
} else {
f[i][j] = f[i][j - c] + 1;
g[i][j] = j - c;
}
}
}
if (f[9][target] < 0) {
return "0";
}
StringBuilder sb = new StringBuilder();
for (int i = 9, j = target; i > 0;) {
if (j == g[i][j]) {
--i;
} else {
sb.append(i);
j = g[i][j];
}
}
return sb.toString();
}
}
|
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
29
30
31
32
33
34
| class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
const int inf = 1 << 30;
vector<vector<int>> f(10, vector<int>(target + 1, -inf));
vector<vector<int>> g(10, vector<int>(target + 1));
f[0][0] = 0;
for (int i = 1; i <= 9; ++i) {
int c = cost[i - 1];
for (int j = 0; j <= target; ++j) {
if (j < c || f[i][j - c] + 1 < f[i - 1][j]) {
f[i][j] = f[i - 1][j];
g[i][j] = j;
} else {
f[i][j] = f[i][j - c] + 1;
g[i][j] = j - c;
}
}
}
if (f[9][target] < 0) {
return "0";
}
string ans;
for (int i = 9, j = target; i;) {
if (g[i][j] == j) {
--i;
} else {
ans += '0' + i;
j = g[i][j];
}
}
return ans;
}
};
|
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
29
30
31
32
33
34
35
36
37
38
| func largestNumber(cost []int, target int) string {
const inf = 1 << 30
f := make([][]int, 10)
g := make([][]int, 10)
for i := range f {
f[i] = make([]int, target+1)
g[i] = make([]int, target+1)
for j := range f[i] {
f[i][j] = -inf
}
}
f[0][0] = 0
for i := 1; i <= 9; i++ {
c := cost[i-1]
for j := 0; j <= target; j++ {
if j < c || f[i][j-c]+1 < f[i-1][j] {
f[i][j] = f[i-1][j]
g[i][j] = j
} else {
f[i][j] = f[i][j-c] + 1
g[i][j] = j - c
}
}
}
if f[9][target] < 0 {
return "0"
}
ans := []byte{}
for i, j := 9, target; i > 0; {
if g[i][j] == j {
i--
} else {
ans = append(ans, '0'+byte(i))
j = g[i][j]
}
}
return string(ans)
}
|
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
29
30
31
32
33
34
35
| function largestNumber(cost: number[], target: number): string {
const inf = 1 << 30;
const f: number[][] = Array(10)
.fill(0)
.map(() => Array(target + 1).fill(-inf));
const g: number[][] = Array(10)
.fill(0)
.map(() => Array(target + 1).fill(0));
f[0][0] = 0;
for (let i = 1; i <= 9; ++i) {
const c = cost[i - 1];
for (let j = 0; j <= target; ++j) {
if (j < c || f[i][j - c] + 1 < f[i - 1][j]) {
f[i][j] = f[i - 1][j];
g[i][j] = j;
} else {
f[i][j] = f[i][j - c] + 1;
g[i][j] = j - c;
}
}
}
if (f[9][target] < 0) {
return '0';
}
const ans: number[] = [];
for (let i = 9, j = target; i; ) {
if (g[i][j] === j) {
--i;
} else {
ans.push(i);
j = g[i][j];
}
}
return ans.join('');
}
|
