题目大意：
数位成本和为目标值的最大数字
给你一个整数数组 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 == 91 <= cost[i] <= 50001 <= target <= 5000
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1449
解题思路分析：
这道题实际上有些类似于背包问题。target相当于背包容量，数字1-9相当于9个不同的物品，而每个数字的cost则相当于物品的体积。对于这类问题，是标准的动态规划思路，对于动态规划DP问题，我习惯使用递归加记忆数组的形式来解题。
首先我们定义一个递归函数，参数是当前的target。递归返回值为当前target下能够组成的最大数字。先看一下递归函数的终止条件：当target等于0时，说明我们已经消耗完了所有target，此时返回空字符串即可。另外如果target大于0，并且数字1-9的cost都大于target时，说明当前递归路径下无论如何我们也无法凑够总cost等于target的方法，此时返回字符串”0″。
递归函数中，我们从数字1循环到9，如果当前数字的cost小于target，说明我们可以选择当前数字，选择后，我们将target减去当前cost，并继续向下层递归。如果下层递归函数的返回值是”0″，说明当前选择方式无法得到合理解，跳过当前循环。反之递归函数的返回值加上当前数字即是当前循环的一个结果。循环完9个数字后，最大的一个结果即是当前递归的返回值。
另外需要注意一点，比较String形式数字的大小时，不能单纯的使用字典顺序来比较，而是要先比较字符串长度，较长的一方数字更大，如果两个字符串长度相同时再去比较字典顺序即可。
最后再考虑记忆数组。记忆数组的维数取决于递归函数中可变参数的数量。本题中可变的参数只有target一个，因此我们定义一个一维记忆数组即可，记忆数组的值为对应递归函数的返回结果。
实现代码：
String[] memo; // 记忆数组
public String largestNumber(int[] cost, int target) {
memo=new String[target+1]; // 初始化记忆数组
return help(cost,target); // 递归求解
}
String help(int[] cost, int target){
if(target==0) return ""; // target为0，返回空
// 如果记忆数组中存在当前解，返回记忆数组中的值
if(memo[target]!=null) return memo[target];
// 返回结果
String max="";
// 循环数字1-9（下标0-8）
for(int i=0;i<cost.length;i++){
// 如果当前数字的下标小于target
if(cost[i]<=target){
// 利用target减去当前cost后，递归至子问题
String temp = help(cost,target-cost[i]);
// 如果子问题结果是"0"，代表当前选择为不合理解，跳过
if("0".equals(temp)) continue;
// 将子问题解加上当前选择的数字
temp+=(i+1);
// 如果当前解大于max，更新max值
if(temp.length()>max.length()
||temp.length()==max.length()&&temp.compareTo(max)>=0){
max=temp;
}
}
}
// 如果当前max为空，说明不存在合理解，设置max为"0"
if("".equals(max)) max="0";
// 将当前解存入记忆数组
memo[target]=max;
return max;
}本题解法执行时间为282ms。
Runtime: 282 ms, faster than 19.68% of Java online submissions for Form Largest Integer With Digits That Add up to Target.
Memory Usage: 123.6 MB, less than 100.00% of Java online submissions for Form Largest Integer With Digits That Add up to Target.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1449-form-largest-integer-with-digits-that-add-up-to-target-解题思路分析/