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.
Integer does not have digits 0.

Since the answer may be too large, return it as string.
If there is no way to paint any integer given the condition, return "0".
 
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  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   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's not possible to paint any integer with total cost equal to target.

Example 4:
Input: cost = [6,10,15,40,40,40,40,40,40], target = 47
Output: "32211"

 
Constraints:

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        

Solutions:
class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		dp = [0] + [-target] * target
		for t in range(1, target + 1):
			dp[t] = max([dp[t - i] for i in cost if i <= t] + [dp[t]]) + 1
		if dp[-1] <= 0:
			return '0'
		res = ''
		for i in range(8, -1, -1):
			while target >= cost[i] and dp[target - cost[i]] == dp[target] - 1:
				res += str(i + 1)
				target -= cost[i]
		return res


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:

		@lru_cache(None)
		def dfs(c):
			if c == 0:
				return 0
			ans = -float('inf')
			for i in range(9):
				if cost[i] <= c:
					ans = max(ans, 10 * dfs(c - cost[i]) + i + 1)
			return ans
		res = dfs(target)
		return str(res) if res > 0 else '0'


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		dp = [0] + [-1] * (target + 5000)
		for t in range(1, target + 1):
			dp[t] = max((dp[t - c] * 10 + i + 1 for (i, c) in enumerate(cost)))
		return str(max(dp[t], 0))


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:

		def memo(f):
			dic = {}

			def f_alt(*args):
				if args not in dic:
					dic[args] = f(*args)
				return dic[args]
			return f_alt
		key = lambda s: (len(s), s)
		cands = {}
		for (i, c) in enumerate(cost):
			cands[c] = i + 1

		@memo
		def f(tar):
			if tar == 0:
				return 0
			if tar > 0:
				ans = 0
				for c in cands:
					if f(tar - c) != None:
						ans = max(ans, 10 * f(tar - c) + cands[c])
				return ans or None
		return str(f(target) or 0)


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		dp = [float('-inf')] * (target + 1)
		dp[0] = 0
		for i in range(1, 10):
			for j in range(1, target + 1):
				c = cost[9 - i]
				if c <= j:
					dp[j] = max(dp[j - c] * 10 + (10 - i), dp[j])
		return str(dp[target]) if str(dp[target]) != '-inf' else '0'


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		dp = [0]
		for i in range(1, target + 1):
			result = 0
			for (j, c) in enumerate(cost):
				if i < c:
					continue
				if dp[i - c] == 0 and i != c:
					continue
				result = max(result, 10 * dp[i - c] + j + 1)
			dp.append(result)
		return str(dp[-1])


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		cache = {}

		def helper(remaining):
			if remaining == 0:
				return ''
			if remaining in cache:
				return cache[remaining]
			maximum = '0'
			for i in range(len(cost)):
				if cost[i] > remaining:
					continue
				result = helper(remaining - cost[i])
				if result == '0':
					continue
				maximum = larger(maximum, str(i + 1) + result)
			cache[remaining] = maximum
			return maximum

		def larger(a, b):
			if len(a) > len(b):
				return a
			if len(a) < len(b):
				return b
			return max(a, b)
		return helper(target)


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		dp = [0] * (target + 1)
		for t in range(1, target + 1):
			for (d, c) in zip(range(1, len(cost) + 1), cost):
				if t == c:
					dp[t] = max(dp[t], d)
				if c < t and dp[t - c] != 0:
					dp[t] = max(dp[t], dp[t - c] * 10 + d)
		return str(dp[target])


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		self.min_cost = min(cost)
		self.cost = cost
		self.mem = dict()
		rv = self.dfs(target)
		if rv is None:
			return '0'
		return rv

	def dfs(self, target):
		if target == 0:
			return ''
		elif target < self.min_cost:
			return None
		key = target
		if key in self.mem:
			return self.mem[key]
		res = ''
		for (i, c) in enumerate(self.cost):
			rv = self.dfs(target - c)
			if rv != None:
				res = self.get_max(res, str(i + 1) + rv)
		if res == '':
			res = None
		self.mem[key] = res
		return res

	def get_max(self, s1, s2):
		if len(s1) != len(s2):
			if len(s1) > len(s2):
				return s1
			return s2
		if s1 > s2:
			return s1
		return s2


from typing import List
import numpy
import functools

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		cache = {}

		def solve(remaining):
			if not remaining:
				return ''
			if remaining in cache:
				return cache[remaining]
			maxium = '0'
			for i in range(len(cost)):
				if cost[i] > remaining:
					continue
				result = solve(remaining - cost[i])
				if result == '0':
					continue
				maxium = larger(maxium, str(i + 1) + result)
				pass
			cache[remaining] = maxium
			return maxium
			pass

		def larger(a, b):
			if len(a) > len(b):
				return a
			if len(a) < len(b):
				return b
			return max(a, b)
		return solve(target)


from functools import lru_cache

class Solution:

	def largestNumber(self, cost, target):
		dp = [0] + [-1] * (target + 5000)
		for t in range(1, target + 1):
			dp[t] = max((dp[t - c] * 10 + i + 1 for (i, c) in enumerate(cost)))
		return str(max(dp[t], 0))


def dp(costs, target, mem):
	if target == 0:
		return ''
	elif target in mem:
		return mem[target]
	res = ''
	for i in range(len(costs)):
		if target - costs[i] >= 0:
			current = dp(costs, target - costs[i], mem)
			if current is not None:
				res = max([res, str(i + 1) + current], key=lambda x: (len(x), x))
	mem[target] = res if res != '' else None
	return res if res != '' else None

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		result = dp(cost, target, {})
		return result if result != '' and result is not None else '0'


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		Memo = {}
		Min = min(cost)
		Memo[0] = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

		def dfs(remain):
			if remain in Memo:
				return Memo[remain]
			if remain < Min:
				Memo[remain] = [0, 0, 0, 0, 0, 0, 0, 0, 0, -10000000]
				return [0, 0, 0, 0, 0, 0, 0, 0, 0, -10000000]
			Max = [0, 0, 0, 0, 0, 0, 0, 0, 0, -10000000]
			flag = False
			for (i, c) in enumerate(cost):
				tmp = dfs(remain - c)
				if tmp[-1] != -10000000:
					flag = True
					newtmp = tmp[:i] + [tmp[i] + 1] + tmp[i + 1:-1] + [tmp[-1] + 1]
					for j in range(9, -1, -1):
						if newtmp[j] > Max[j]:
							Max = newtmp
							break
						elif newtmp[j] == Max[j]:
							continue
						else:
							break
			Memo[remain] = Max
			return Max
		r = dfs(target)
		if r[-1] == -10000000:
			return '0'
		else:
			rs = ''
			for k in range(8, -1, -1):
				rs += str(k + 1) * r[k]
		return rs


def prune(costs):
	ans = []
	for (ind, elem) in enumerate(costs):
		if any((costs[i] + costs[j] == elem for i in range(ind) for j in range(ind))):
			pass
		else:
			ans.append(elem)
	return ans

def find_longest_combos(costs, start, prefix, left, max_yets):
	if start == len(costs):
		if left == 0 and len(prefix) >= max_yets[0]:
			max_yets[0] = len(prefix)
			yield prefix[:]
	else:
		theoretical_max_length = len(prefix) + left // costs[start]
		if theoretical_max_length < max_yets[0]:
			return
		if costs[start] <= left:
			prefix.append(costs[start])
			yield from find_longest_combos(costs, start, prefix, left - costs[start], max_yets)
			prefix.pop()
		if True:
			yield from find_longest_combos(costs, start + 1, prefix, left, max_yets)

def rlencode(arr):
	ans = []
	for elem in arr:
		if ans and ans[-1][0] == elem:
			ans[-1] = (ans[-1][0], ans[-1][1] + 1)
		else:
			ans.append((elem, 1))
	return ans

def encode(digit_choices, combo):
	return sorted([(digit_choices[elem], freq) for (elem, freq) in combo], reverse=True)

def write(rle):
	ans = []
	for (elem, freq) in rle:
		for _ in range(freq):
			ans.append(elem)
	return ''.join(map(str, ans))

def gcd(a, b):
	(a, b) = (min(a, b), max(a, b))
	while a > 0:
		(a, b) = (b % a, a)
	return b

def gcdall(arr):
	ans = arr[0]
	for elem in arr:
		ans = gcd(ans, elem)
	return ans

def obviously_unsatisfactory(cost, target):
	if min(cost) > target:
		return True
	if target % gcdall(cost) != 0:
		return True
	return False

def largest_num(cost, target):
	if obviously_unsatisfactory(cost, target):
		return '0'
	costs = sorted(list(set(cost)))
	costs = prune(costs)
	combinations = list(find_longest_combos(costs, 0, [], target, [0]))
	if not combinations:
		return '0'
	max_length = max(map(len, combinations))
	combinations = (c for c in combinations if len(c) == max_length)
	digit_choices = {}
	for (i, c) in enumerate(cost):
		digit_choices[c] = i + 1
	combinations = map(rlencode, combinations)
	combinations = (encode(digit_choices, combo) for combo in combinations)
	return write(max(combinations))

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		return largest_num(cost, target)


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:

		@lru_cache(None)
		def rec(rem):
			if rem <= 0:
				return 0 if rem == 0 else -math.inf
			ans = -math.inf
			for c in cost:
				ans = max(ans, rec(rem - c) + 1)
			return ans
		ln = rec(target)
		if ln <= 0:
			return '0'

		def path(rem, now):
			if rem <= 0:
				return now if rem == 0 else ''
			for (i, c) in enumerate(reversed(cost)):
				if rec(rem - c) + 1 == rec(rem):
					return path(rem - c, now + str(9 - i))
			return ''
		ans = path(target, '')
		print(ans)
		return ans


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		cost_to_digit = {val: str(index + 1) for (index, val) in enumerate(cost)}
		cost = sorted(cost_to_digit.keys())

		@lru_cache(None)
		def helper(target: int) -> str:
			if target < cost[0]:
				return None
			max_number = None if target not in cost_to_digit else cost_to_digit[target]
			for c in cost:
				if c > target:
					break
				curr_number = helper(target - c)
				if curr_number is None:
					continue
				curr_number = ''.join(sorted(cost_to_digit[c] + curr_number, reverse=True))
				max_number = curr_number if max_number is None or len(curr_number) > len(max_number) or (len(curr_number) == len(max_number) and curr_number > max_number) else max_number
			return max_number
		ans = helper(target)
		return ans if ans else '0'


from functools import lru_cache

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		ss = set()
		for (i, c) in enumerate(reversed(cost)):
			if c not in ss:
				ss.add(c)
			else:
				cost[~i] = float('inf')
		cost = list(((cost[i], str(i + 1)) for i in range(9) if cost[i] != float('inf')))
		dp = [[] for _ in range(target + 1)]
		for i in range(1, target + 1):
			for (c, d) in cost:
				if i - c == 0 or (i - c > 0 and len(dp[i - c])):
					tmp = sorted(dp[i - c] + [d], reverse=1)
					if len(dp[i - c]) + 1 > len(dp[i]):
						dp[i] = tmp
					elif len(dp[i - c]) + 1 == len(dp[i]):
						if tmp > dp[i]:
							dp[i] = tmp
		return ''.join(dp[-1]) if dp[-1] else '0'


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		dp = [0] + [-float('inf')] * (5000 + target)
		for i in range(1, target + 1):
			for (j, c) in enumerate(cost):
				dp[i] = max(dp[i], 10 * dp[i - c] + j + 1)
		print(dp[:target + 1])
		return str(max(dp[target], 0))


from functools import lru_cache

class Solution:

	@lru_cache(None)
	def recursive(self, k):
		if k == 0:
			return ''
		ans = []
		for x in self.d:
			if x <= k:
				r = self.recursive(k - x)
				if r != '0':
					ans.append(self.d[x] + r)
		return str(max(map(int, ans))) if ans else '0'

	def largestNumber(self, cost: List[int], target: int) -> str:
		self.d = {}
		for (i, x) in enumerate(cost):
			self.d[x] = str(i + 1)
		self.recursive.cache_clear()
		return self.recursive(target)


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		for i in range(len(cost)):
			for j in range(len(cost) - 1, i, -1):
				if cost[j] and (not cost[i] % cost[j]):
					cost[i] = 0
					break
		costMap = {e: k + 1 for (k, e) in enumerate(cost) if e}
		print((costMap, cost))

		def getMaxList(s1, s2):
			if s2 == None:
				return ''
			return ''.join(sorted(s1 + s2, reverse=True))

		def dfs(c):
			if c in dp:
				return dp[c]
			if c == 0:
				return ''
			elif c < 0:
				return None
			strs = [getMaxList(str(i), dfs(c - cost[i - 1])) for i in range(1, 10) if cost[i - 1] in costMap]
			if not any(strs):
				dp[c] = None
				return None
			l = max(list(map(len, strs)))
			newStr = sorted(strs)
			for i in range(len(strs) - 1, -1, -1):
				if len(newStr[i]) == l:
					dp[c] = newStr[i]
					return dp[c]
		dp = {}
		res = dfs(target)
		return res if res else '0'


def cmp(s, t):
	if len(s) != len(t):
		return len(s) < len(t)
	for i in range(len(s)):
		if s[i] != t[i]:
			return s[i] < t[i]
	return False

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		best = {}
		for i in range(len(cost) - 1, -1, -1):
			digit = i + 1
			if cost[i] not in best:
				best[cost[i]] = digit
		keys = sorted(list(best.keys()), key=lambda x: best[x], reverse=True)

		@lru_cache(None)
		def f(t, idx):
			if t == 0:
				return ''
			if t < 0 or idx == len(keys):
				return '0'
			k = keys[idx]
			b = '0'
			best_ct = 0
			for ct in range(t // k, -1, -1):
				r = f(t - k * ct, idx + 1)
				if r != '0':
					if b == '0' or ct + len(r) > best_ct + len(b):
						b = r
						best_ct = ct
			return str(best[k]) * best_ct + b
		return f(target, 0)


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		d = {i: -1 for i in cost}
		for i in range(1, len(cost) + 1):
			d[cost[i - 1]] = max(d[cost[i - 1]], i)
		dp = ['-1'] * (target + 1)
		cost = list(set(cost))
		cost.sort()
		for i in d:
			try:
				dp[i] = str(d[i])
			except:
				pass
		for i in range(1, target + 1):
			for j in cost:
				if i - j > 0:
					if dp[i - j] != '-1':
						dp[i] = str(max(int(dp[i - j] + str(d[j])), int(dp[i])))
					else:
						try:
							dp[i] = str(max(int(dp[i]), d[i]))
						except:
							pass
				else:
					break
		if dp[target] == '-1':
			return '0'
		return dp[target]


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		t = target
		dp = [['0'] for _ in range(t + 1)]
		dp[0] = ['']
		for i in range(1, t + 1):
			for j in range(9):
				l1 = len(dp[i])
				l1 = 0 if dp[i] == ['0'] else l1
				l2 = len(dp[i - cost[j]]) + 1 if i >= cost[j] else 0
				c = dp[i - cost[j]] if i >= cost[j] else ['0']
				if l1 <= l2:
					dp[i] = c + [str(j + 1)] if c != ['0'] else ['0']
		ans = ''.join(sorted(dp[t])[::-1])
		return ans


def cmp(a, b):
	(ad, bd) = ({}, {})
	for i in range(0, len(a), 2):
		ad[a[i]] = a[i + 1]
	for i in range(0, len(b), 2):
		bd[b[i]] = b[i + 1]
	sad = sum(ad.values())
	sbd = sum(bd.values())
	if sad != sbd:
		return sad < sbd
	al = sorted(list(ad.keys()), reverse=True)
	bl = sorted(list(bd.keys()), reverse=True)
	for i in range(1 + min(len(al), len(bl))):
		if al[i] == bl[i]:
			c = al[i]
			if ad[c] != bd[c]:
				return ad[c] < bd[c]
		else:
			return al[i] < bl[i]
	return False

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		best = {}
		for i in range(len(cost) - 1, -1, -1):
			digit = i + 1
			if cost[i] not in best:
				best[cost[i]] = digit
		x = sorted(best.keys())
		y = sorted(list(best.values()), reverse=True)

		@lru_cache(None)
		def best_path(t, idx):
			if t == 0:
				return tuple()
			if idx == len(x):
				return None
			ret = None
			bi = -1
			for i in range(t // x[idx], -1, -1):
				y = best_path(t - i * x[idx], idx + 1)
				if y is not None:
					if i > 0:
						y = (best[x[idx]], i) + y
					if bi == -1 or cmp(ret, y):
						ret = y
						bi = i
			return ret
		r = best_path(target, 0)
		if r is None:
			return '0'
		unpacked = {}
		for i in range(0, len(r), 2):
			unpacked[r[i]] = r[i + 1]
		s = ''
		for digit in y:
			if digit in unpacked:
				s += str(digit) * unpacked[digit]
		return s


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		q = [(0, -target)]
		visited = {}
		costs = dict(zip(range(1, 10), cost))
		for (i, a) in enumerate(cost, 1):
			for b in cost[i:]:
				if b <= a and (not a % b):
					del costs[i]
					break
		while q:
			(n, hp) = heapq.heappop(q)
			n = -n
			hp = -hp
			if hp < 0:
				continue
			if visited.get(hp, -1) >= n:
				continue
			visited[hp] = n
			for c in costs:
				if costs[c] <= hp:
					heapq.heappush(q, (-(n * 10 + c), -(hp - costs[c])))
		return str(visited.get(0, 0))


class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:
		return self.helper(cost, target, {})

	def helper(self, cost, target, visited):
		if target == 0:
			return ''
		if target in visited:
			return visited[target]
		ans = '0'
		for i in range(1, 10):
			if target >= cost[i - 1]:
				prev = self.helper(cost, target - cost[i - 1], visited)
				if prev != '0':
					curr = str(i) + prev
					if len(curr) >= len(ans) and int(curr) > int(ans):
						ans = curr
		visited[target] = ans
		return ans


from functools import lru_cache

class Solution:

	def largestNumber(self, cost: List[int], target: int) -> str:

		@lru_cache(None)
		def dp(index, remain):
			if remain == 0:
				return ''
			elif remain < 0 or index > len(cost):
				return '0'
			take = str(index) + dp(1, remain - cost[index - 1])
			skip = dp(index + 1, remain)
			return get_bigger(take, skip)

		def get_bigger(a, b):
			if '0' in a:
				return b
			elif '0' in b:
				return a
			elif int(a) > int(b):
				return a
			else:
				return b
		ans = dp(1, target)
		return ans if '0' not in ans else '0'