How to improve it's algorithm

Question

Yeah if I input a large num,it timed out.So anyone help me to improve it's algorithm!Thanks
https://code.sololearn.com/cbblP6b9x5mS/?ref=app

Answer 1

Shirt it is a classical dynamic programming problem.

Here is the solution 👇
time complexity = O(n)
auxiliary space required is also O(n)

https://code.sololearn.com/cuG06qK3ru9B/?ref=app

Answer 2

How can we improvise the algorithm if we don't know what exactly is the question ?

Answer 3

Thanks bro you are so cool

Answer 4

Ops I forget 😅 the question is one day you wemt shopping and shopkeeper gave you %d 💰 (such as 20);and you only can choose 1$,5$,20$ three types .the question is it has how many combinations? (20 money have 6 combinations)