What is the primary approach to solving the 'Form Largest Integer With Digits That Add up to Target' problem?

The problem is typically solved using dynamic programming with state transitions to maximize the number of digits within a target cost.

How can I optimize the time complexity of this problem?

The time complexity can be optimized by ensuring efficient state transitions within the DP array, reducing unnecessary recalculations.

What happens if no valid integer can be formed under the target cost?

In that case, the function should return '0', indicating that it is impossible to paint any integer under the given constraints.

How do I handle the edge case where the target cost is too small?

For edge cases where the target cost is too small to paint any digit, the result should immediately be '0'.

What would happen if the array length or the cost values were larger?

The dynamic programming approach still applies, but larger inputs may require optimizations in both time and space complexity to handle larger target values.

#1449

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：给当前结果添加一个数位（ i + 1 ）的成本为 cost[i] （ cost 数组下标从 0 开始）。总成本必须恰好等于 target 。添加的数位中没有数字 0 。由于答案可能会很大，请你…

数组动态规划

题目描述

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 "0" 。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"

提示：

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

lightbulb

解题思路

方法一：动态规划（背包问题）

我们定义 $f[i][j]$ 表示使用前 $i$ 个数位，花费恰好为 $j$ 的情况下，能够得到的最大位数。初始时， $f[0][0]=0$ ，其余为 $-\infty$ 。

考虑 $f[i][j]$ ，第 $i$ 个数的花费为 $c = cost[i-1]$ ，如果 $j \lt c$ ，那么我们无法选取第 $i$ 个数位，此时有 $f[i][j]=f[i-1][j]$ ；否则我们可以选取第 $i$ 个数位，此时有 $f[i][j]=f[i][j-c]+1$ 。

如果 $f[9][target] \lt 0$ ，那么说明无法得到满足要求的整数，返回 "0" 即可。

否则，我们需要从 $f[9][target]$ 开始，倒推出每一位的数字。我们可以使用一个数组 $g[i][j]$ 记录 $f[i][j]$ 的上一个状态，从而倒推出每一位的数字。

具体地，在状态转移时，如果 $j \lt c$ ，或者 $f[i][j-c]+1 \lt f[i-1][j]$ ，那么我们不选取第 $i$ 个数位，此时有 $g[i][j]=j$ ；否则我们选取第 $i$ 个数位，此时有 $g[i][j]=j-c$ 。

最后，我们定义 $i = 9$ , $j = target$ ，从 $g[i][j]$ 开始不断地倒推，如果 $g[i][j]=j$ ，说明数字 $i$ 没有被选取，我们令 $i = i - 1$ ；否则说明数字 $i$ 被选取，我们令 $j = g[i][j]$ ，并将数字 $i$ 加入答案中。重复上述操作，直到 $i = 0$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ ，其中 $m$ 和 $n$ 分别为数组 $cost$ 和 $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

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)

speed

复杂度分析

指标	值
时间	complexity depends on the number of digits (9 in this case) and the target cost. The space complexity is dependent on the size of the `dp` array, which is proportional to the target value. Given the constraints, both complexities should scale reasonably well, especially with optimized state transitions.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of dynamic programming and its efficient use in state transitions.
question_mark
Check for clear explanation of greedy strategies within the DP solution to maximize the integer value.
question_mark
Gauge familiarity with handling edge cases where no valid number can be formed.

warning

常见陷阱

外企场景

error
Not properly updating the DP array for each state transition can lead to incorrect results.
error
Overcomplicating the solution by using inefficient data structures or failing to optimize the transitions.
error
Ignoring edge cases where it's impossible to form any valid integer, resulting in incorrect output.

swap_horiz

进阶变体

外企场景

arrow_right_alt
How would you modify the solution if there were more digits or different constraints?
arrow_right_alt
Can you optimize the space complexity further by reducing the size of the DP array?
arrow_right_alt
What changes would you make if the costs were dynamic or changed during computation?

help

常见问题

外企场景

继续练习

#1444 切披萨的方案数 #1458 两个子序列的最大点积 #1463 摘樱桃 II