LegendRanger's blog

dp problem.find the number of ways
By LegendRanger, history, 7 months ago, In English

You are given three coins numbered 1, 2, and 3. Your objective is to make the number n=10 using these coins, but you cannot select the same coin consecutively. For instance, combinations like 1+2+2 or 2+2+3 are not valid but 1+2+3 or 1+2+1 valid. coins can be any type of coins and n can be any number. Find the number of ways to achieve this.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LegendRanger (previous revision, new revision, compare).

→ Reply
»
7 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

the solution depends on maximum value of $$$n$$$ and the maximum number of types of coins.

a simple $$$dp$$$ solution would be:

let $$$dp_{i,k}$$$ be the number of ways to make the number $$$i$$$ and last coin that was used is of type $$$k$$$.

$$$dp_{i,k}$$$ = $$$\sum_{type \neq k}$$$ $$$dp_{i-k,type}$$$

and the answer would be $$$\sum_{type}$$$ $$$dp_{n,type}$$$

→ Reply