Array
Dynamic Programming
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 == 9
1 <= cost[i], target <= 5000
Solutions
Solution 1
Python3 Java C++ Go TypeScript
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 ( '' );
}
GitHub