CODEWITHSUNDEEP
algorithmrecursiondynamic-programming
Katerina Giorgallou
Katerina Giorgallou

Reputation: 11

Dynamic Programming problems with coins

There is an array of š‘› coins with values š¶ = [š‘1, š‘2, ā€¦ , š‘š‘›]. The prices are positive integers and repetitions are allowed. For example, one possible sequence of coins is as follows: š¶7 = [5, 20, 2, 20, 1, 10, 50]. Your goal is to collect the maximum amount of money with the limitation that you will not get two coins lying next to each other in the original row. For example, if get coin 10 from š¶7, then you cannot get coins 1 or 50.

Can you find me the recursion equation for this problem?

I tried this but I'm not sure:

M(i) = max{ M(iāˆ’1), if we take the coin i
            M(iāˆ’2)+C[i], if we don't take the coin i

Upvotes: 1

Views: 98

Answers (1)

ggorlen
ggorlen

Reputation: 56965

Your solution looks right to me, except your labels are reversed. + C[i] corresponds to taking coin i, not the other way around.

I'd also add a base case if you haven't already.

Note that this is the house robber problem, so there are a ton of solutions online you can compare against.

See also: How do I solve the Coin Row problem using dynamic programming?.

Upvotes: 0

Related Questions