HardNo. 1449
Form Largest Integer With Digits That Add up to Target — LeetCode 1449 Python Solution
- Pattern
- Dynamic Programming
- Topics
- Array, Dynamic Programming
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
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)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Dynamic Programming
Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 1449. Form Largest Integer With Digits That Add up to Target is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.
The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1444 | Number of Ways of Cutting a Pizza | Hard |
| 1458 | Max Dot Product of Two Subsequences | Hard |
| 0045 | Jump Game II | Medium |
| 0053 | Maximum Subarray | Medium |
| 0055 | Jump Game | Medium |
| 0063 | Unique Paths II | Medium |
Frequently asked questions
- How hard is LeetCode 1449. Form Largest Integer With Digits That Add up to Target?
LeetCode 1449. Form Largest Integer With Digits That Add up to Target is rated Hard on LeetCode.
- What topics does LeetCode 1449. Form Largest Integer With Digits That Add up to Target cover?
LeetCode 1449. Form Largest Integer With Digits That Add up to Target is tagged Array and Dynamic Programming on LeetCode.