<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>

typedef vector<vector<string>> vv_str;
typedef vector<string> v_str;
class Solution {
public:
    
    bool greater(string &a,string &b)
    {
        if(a.length() > b.length())
            return true;
        else if(a.length() < b.length())
            return false;
        else
        {
            int len = a.length();
            for(int i = len-1;i>=0;i--)
            {
                if(a[i] > b[i])
                    return true;
                else if(a[i] < b[i])
                    return false;
            }
        }
        return true;
    }

    char get_char(int num)
    {
        int res = num + (int)'0';
        return (char)res;
    }

    string largestNumber(vector<int>& cost, int target) {
        vv_str dp(target+1,v_str(10,""));
        for(int curr = 1;curr<target+1;curr++)
        {
            int maxint = 1;
            string ans = "";
            if(curr%cost[maxint-1]==0)
            {
                int countdig = curr/cost[maxint-1];
                for(int i = 0;i<countdig;i++)
                {
                    ans.push_back('1');
                }
            }
            dp[curr][maxint-1] = ans;
        }
        for(int curr = 1;curr<target+1;curr++)
        {
            for(int maxint = 2 ; maxint<=9 ; maxint++)
            {
                int intcost = cost[maxint-1];
                dp[curr][maxint-1] = dp[curr][maxint-2];
                if((intcost <= curr) && (((dp[curr-intcost][maxint-1] == "") && ((curr-intcost) == 0)) || !(dp[curr-intcost][maxint-1] == "")) )
                {
                    string newcand = dp[curr-intcost][maxint-1];
                    newcand.push_back(get_char(maxint));
                    // cout<<"new cand "<<curr<<" "<<maxint<<" "<<newcand<<endl;
                    bool ver = greater(newcand,dp[curr][maxint-1]);
                    // cout<<newcand<<" "<<(dp[curr][maxint-1])<<" "<<ver<<endl;
                    if(greater(newcand,dp[curr][maxint-1]))
                    {
                        dp[curr][maxint-1] = newcand;
                    }
                }
            }
        }
        // cout<<"last"<<endl;
        // for(int i = 0;i<target+1;i++)
        // {
        //     for(int j = 0;j<9;j++)
        //     {
        //         cout<<i<<" "<<j+1<<" "<<dp[i][j]<<endl;
        //     }
        // }
        if(dp[target][8] == "")
            return "0";
        int start = 0,end = dp[target][8].length()-1;
        while(start < end)
        {
            char temp = dp[target][8][start];
            dp[target][8][start] = dp[target][8][end];
            dp[target][8][end] = temp;
            start++;
            end--;
        }
        return dp[target][8];
        
    }
};
693436