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

<ul>
	<li>The cost of painting a digit <code>(i + 1)</code> is given by <code>cost[i]</code> (<strong>0-indexed</strong>).</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>

<p>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>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> cost = [4,3,2,5,6,7,2,5,5], target = 9
<strong>Output:</strong> &quot;7772&quot;
<strong>Explanation:</strong> 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.
<strong>Digit    cost</strong>
  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>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> cost = [7,6,5,5,5,6,8,7,8], target = 12
<strong>Output:</strong> &quot;85&quot;
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class Solution {
public:
    // void printArr(string dp[10][], int target){
    //     for(int i = 0; i<10; i++){
    //         for(int j = 0; j<=target; j++){
    //             cout<<dp[i][j]<<" ";
    //         }
    //         cout<<'\n';
    //     }
    //     cout<<'\n';
    // }
    void printDp(vector<string> &arr){
        for(int i = 0; i<arr.size(); i++) cout<<arr[i]<<",";
        cout<<'\n';
    }
    string getString(string &s1, string &s2){
        int val = compareNumberStrings(s1, s2);
        if(val > 0) return s1;
        return s2;
    }
    int compareNumberStrings(string& num1, string& num2) {
        if (num1.length() > num2.length()) {
            return 1;
        } else if (num1.length() < num2.length()) {
            return -1;
        } else {
            return num1.compare(num2);
        }
    }
    string largestNumber(vector<int>& cost, int target) {
        vector<string> dp(target+1, "");
        for(int i = 9; i>=1; i--){
            char ch = i+'0';
            int val = cost[i-1];
            vector<string> temp(target+1, "");
            for(int j = 1; j<= target; j++){
                if(j==val){
                    string s1 = dp[j];
                    string s2 = "";
                    s2+=ch;
                    temp[j] = getString(s1, s2);
                }
                else if(j-val>0){
                    string s1 = dp[j];
                    string s2 = temp[j-val];
                    if(s2 == "") temp[j] = dp[j];
                    else {
                        s2+=ch;
                        temp[j] = getString(s1, s2);
                    }
                }
                else temp[j] = dp[j];
            }
            dp = temp;
        }
        return dp[target] == "" ? "0" : dp[target];
    }
};
461191