form-largest-integer-with-digits-that-add-up-to-target

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an array of integers <code>cost</code> and an integer <code>target</code>, return the maximum integer you can paint under the following rules:

<ul>
	<li>The cost of painting a digit <code>(i + 1)</code> is given by <code>cost[i]</code> (0-indexed).</li>
	<li>The total cost used must be equal to <code>target</code>.</li>
	<li>The integer does not have <code>0</code> digits.</li>
</ul>

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 <code>&quot;0&quot;</code>.

&nbsp;
Example 1:

<pre>
Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: &quot;7772&quot;
Explanation: The cost to paint the digit &#39;7&#39; is 2, and the digit &#39;2&#39; is 3. Then cost(&quot;7772&quot;) = 2*3+ 3*1 = 9. You could also paint &quot;977&quot;, but &quot;7772&quot; is the largest number.
Digit cost
 1 -&gt; 4
 2 -&gt; 3
 3 -&gt; 2
 4 -&gt; 5
 5 -&gt; 6
 6 -&gt; 7
 7 -&gt; 2
 8 -&gt; 5
 9 -&gt; 5
</pre>

Example 2:

<pre>
Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: &quot;85&quot;
Explanation: The cost to paint the digit &#39;8&#39; is 7, and the digit &#39;5&#39; is 5. Then cost(&quot;85&quot;) = 7 + 5 = 12.
</pre>

Example 3:

<pre>
Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: &quot;0&quot;
Explanation: It is impossible to paint any integer with total cost equal to target.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>cost.length == 9</code></li>
	<li><code>1 &lt;= cost[i], target &lt;= 5000</code></li>
</ul>

largestNumber

Form Largest Integer With Digits That Add up to Target

Array

Dynamic Programming

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

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

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

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

 

示例 1：

<pre>
输入：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
</pre>

示例 2：

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

示例 3：

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

示例 4：

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

 

提示：

<ul>
	<li><code>cost.length == 9</code></li>
	<li><code>1 <= cost[i] <= 5000</code></li>
	<li><code>1 <= target <= 5000</code></li>
</ul>