# 1449. 数位成本和为目标值的最大数字
## 题目描述
```
给你一个整数数组 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 。 "997" 也是满足要求的数字，但 "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
```
## 前置知识
* 数组
* 动态规划
* 背包问题
## 公司
* 暂无
## 思路
由于数组可以重复选择，因此这是一个完全背包问题。
### 01 背包
对于 01 背包问题，我们的套路是：
```py
for i in 0 to N:
for j in 1 to V + 1:
dp[j] = max(dp[j], dp[j - cost[i])
```
而一般我们为了处理边界问题，我们一般会这么写代码：
```py
for i in 1 to N + 1:
# 这里是倒序的，原因在于这里是01背包。
for j in V to 0:
dp[j] = max(dp[j], dp[j - cost[i - 1])
```
其中 dp\[j] 表示只能选择前 i 个物品，背包容量为 j 的情况下，能够获得的最大价值。
> dp\[j] 不是没 i 么？ 其实我这里 i 指的是 dp\[j]当前所处的循环中的 i 值
### 完全背包问题
回到问题，我们这是完全背包问题:
```py
for i in 1 to N + 1:
# 这里不是倒序，原因是我们这里是完全背包问题
for j in 1 to V + 1:
dp[j] = max(dp[j], dp[j - cost[i - 1])
```
### 为什么 01 背包需要倒序，而完全背包则不可以
实际上，这是一个骚操作，我来详细给你讲一下。
其实要回答这个问题，我要先将 01 背包和完全背包退化二维的情况。
对于 01 背包：
```py
for i in 1 to N + 1:
for j in V to 0:
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i - 1])
```
注意等号左边是 i，右边是 i - 1，这很好理解，因为 i 只能取一次嘛。
那么如果我们不降序遍历会怎么样呢？
如图橙色部分表示已经遍历的部分，而让我们去用\[j - cost\[i - 1]] 往前面回溯的时候，实际上回溯的是 dp\[i]j - cost\[i - 1]]，而不是 dp\[i - 1]j - cost\[i - 1]]。
如果是降序就可以了，如图：
这个明白的话，我们继续思考为什么完全背包就要不降序了呢？
我们还是像上面一样写出二维的代码：
```py
for i in 1 to N + 1:
for j in 1 to V + 1:
dp[i][j] = max(dp[i - 1][j], dp[i][j - cost[i - 1])
```
由于 i 可以取无数次，那么正序遍历正好可以满足，如上图。
### 恰好装满 VS 可以不装满
题目有两种可能，一种是要求背包恰好装满，一种是可以不装满（只要不超过容量就行）。而本题是要求`恰好装满`的。而这两种情况仅仅影响我们`dp数组初始化`。
* 恰好装满。只需要初始化 dp\[0] 为 0， 其他初始化为负数即可。
* 可以不装满。 只需要全部初始化为 0，即可，
原因很简单，我多次强调过 dp 数组本质上是记录了一个个自问题。 dp\[0]是一个子问题，dp\[1]是一个子问题。。。
有了上面的知识就不难理解了。 初始化的时候，我们还没有进行任何选择，那么也就是说 dp\[0] = 0，因为我们可以通过什么都不选达到最大值 0。而 dp\[1],dp\[2]...则在当前什么都不选的情况下无法达成，也就是无解，因为为了区分，我们可以用负数来表示，当然你可以用任何可以区分的东西表示，比如 None。
### 回到本题
而这道题和普通的完全背包不一样，这个是选择一个组成的最大数。由小学数学知识`一个数字的全排列中，按照数字降序排列是最大的`，我这里用了一个骚操作，那就是 cost 从后往前遍历，因为后面表示的数字大。
## 代码
```py
class Solution:
def largestNumber(self, cost: List[int], target: int) -> str:
dp = [0] + [float('-inf')] * target
for i in range(9, 0, -1):
for j in range(1, target+1):
if j >= cost[i - 1]:
dp[j] = max(dp[j], (dp[j-cost[i - 1]] * 10) + i)
return str(dp[target]) if dp[target] > 0 else '0'
```
**复杂度分析**
* 时间复杂度：$O(target))$
* 空间复杂度：$O(target)$
## 扩展
最后贴几个我写过的背包问题，让大家看看历史是多么的相似。
 （[322. 硬币找零(完全背包问题)](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/322.coin-change)）
> 这里内外循环和本题正好是反的，我只是为了"秀技"(好玩)，实际上在这里对答案并不影响。
 （[518. 零钱兑换 II](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/518.coin-change-2)）
> 这里内外循环和本题正好是反的，但是这里必须这么做，否则结果是不对的，具体可以点进去链接看我那个题解
所以这两层循环的位置起的实际作用是什么？ 代表的含义有什么不同？
本质上:
```py
for i in 1 to N + 1:
for j in V to 0:
...
```
这种情况选择物品 1 和物品 3（随便举的例子），是一种方式。选择物品 3 个物品 1（注意是有顺序的）是同一种方式。 **原因在于你是固定物品，去扫描容量**。
而：
```py
for j in V to 0:
for i in 1 to N + 1:
...
```
这种情况选择物品 1 和物品 3（随便举的例子），是一种方式。选择物品 3 个物品 1（注意是有顺序的）也是一种方式。**原因在于你是固定容量，去扫描物品**。
**因此总的来说，如果你认为\[1,3]和\[3,1]是一种，那么就用方法 1 的遍历，否则用方法 2。**
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
