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


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


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 "0".

&nbsp;
Example 1:

Input: cost = [4,3,2,5,6,7,2,5,5], target = 9
Output: "7772"
Explanation: The cost to paint the digit '7' is 2, and the digit '2' is 3. Then cost("7772") = 2*3+ 3*1 = 9. You could also paint "977", but "7772" 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


Example 2:

Input: cost = [7,6,5,5,5,6,8,7,8], target = 12
Output: "85"
Explanation: The cost to paint the digit '8' is 7, and the digit '5' is 5. Then cost("85") = 7 + 5 = 12.


Example 3:

Input: cost = [2,4,6,2,4,6,4,4,4], target = 5
Output: "0"
Explanation: It is impossible to paint any integer with total cost equal to target.


&nbsp;
Constraints:


	cost.length == 9
	1 &lt;= cost[i], target &lt;= 5000


from functools import lru_cache
class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        @lru_cache(None)
        def dfs(t):
            if t == 0: return 0
            res = float('-inf')
            for digit in range(1,10):
                if t - cost[digit-1] >= 0:
                    res = max(res, dfs(t - cost[digit-1])*10+digit)
            return res
        res = dfs(target)
        return "0" if res == float('-inf') else str(res)
// Space Complexity = O(N*M) (N == length of cost array and M == target )
// Time Complexity = O(N*M)

class Solution {
    Map<String,String> map =  new HashMap<>();
    String[][] memo;
    public String largestNumber(int[] cost, int target) {
        memo = new String[cost.length+1][target+1];
        
        for( int i = 0;i<=cost.length;i++ ){
            for(int j = 0;j<=target;j++) memo[i][j] = "0";
        }
        
        String res = helper(cost,cost.length-1,target);
        
        return res == "-1" ? "0" : res; 
        
    }
    
    public String helper( int[] cost , int index , int target){
        if(target == 0) {
            return "";
        }
        
        if(target < 0) return "-1";
        
        if(index < 0) return "-1";
        
        if( memo[index][target] != "0") return memo[index][target];
        
        String str1 = (index+1) + helper(cost,cost.length-1,target-cost[index]) ;
        String str2 = helper(cost,index-1,target);
        
        String res = getBigger(str1,str2);
        
        memo[index][target] =  res;
        
        return res;
    }
    
    public String getBigger(String num1 , String num2){
        if( num1.contains("-1") ) return num2;
        if( num2.contains("-1") ) return num1;
        if( num1.length() > num2.length() ) return num1;
        if( num2.length() > num1.length() ) return num2;
        return Double.parseDouble( num1 ) < Double.parseDouble( num2 ) ? num2 : num1;
    }
}
class Solution {
public:
    vector<vector<string>> dp ;
    string largestNumber(vector<int>& cost, int target) {
        dp.resize(10,vector<string>(target+1,"-1"));
        return solve(cost,0,target) ;
    }
    
    string solve(vector<int>& cost,int idx,int target){
        if(!target) return "";
        if(target < 0 || idx >= size(cost)) return "0"; 
        
        if(dp[idx][target]!="-1") return dp[idx][target];
        
        string a = to_string(idx+1) + solve(cost,0,target-cost[idx]);
        string b = solve(cost,idx+1,target);
        
        return dp[idx][target] = a.back() == '0' ? b : b.back() == '0' ? a : size(a) == size(b) ? max(a,b) : size(a) > size(b) ? a : b ;
    }
};
var largestNumber = function(cost, target) {
    const arr = new Array(target+1).fill('#');
    arr[0] = '';
    
    for (let i = 0; i < 9; i++) {
        for (let j = cost[i]; j <= target; j++) {
            if (arr[j-cost[i]] !== '#' && arr[j-cost[i]].length + 1 >= arr[j].length) {
                arr[j] = (i+1).toString().concat(arr[j-cost[i]]);
            }
        }
    }
    
    return arr[target] == '#' ? '0' : arr[target];
};
Form Largest Integer With Digits That Add up to Target