LegendRanger's blog

dp problem.find the number of ways
By LegendRanger, history, 13 days 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

»
13 days 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
»
13 days 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