3 ms·
In the first problem illustrated, I wanted to also get the list of coins. I made this attempt, but this hardly seems elegant. Any comments to make it better?
by vardhanw 8y ago
In the first problem illustrated, I wanted to also get the list of coins. I made this attempt, but this hardly seems elegant. Any comments to make it better?
n=10
denom = [1,3,4]
dp = [-1 for i in range(n+1)]
dpl = [[] for i in range(n+1)]
def f(n):
if dp[n]!= -1:
return dp[n]
ans = 10**10
if n<=0:
return 0
mini=n
for i in denom:
if (n-i)>=0:
new = f(n-i)+1
if new <= ans:
mini=i
ans = new
dpl[n].append(mini)
if mini!=n:
dpl[n] = [item for sublist in [dpl[n], dpl[n-mini]] for item in sublist]
dp[n]=ans
return ans
if __name__ == "__main__":
ans = f(n)
print(ans, dpl)
- pwaivers 8y agoTo be more elegant, you can remove the "dp" array. If you want to keep track of the full list, then you only need to keep track of "dpl". Here is code that I wrote and it works: n = 10 denom = [1, 3, 4] dpl = [[] for i in range(n+1)] def f(n): if dpl[n]: return dpl[n] if n <= 0: return [] ans = list(range(n)) # this is the max size possible for i in denom: if n-i >= 0: new = f(n-i) + [i] # append i to the end of the array if len(new) <= len(ans): ans = new dpl[n] = ans return ans if __name__ == "__main__": sol = f(n) print(sol)