Блог пользователя RaHuL-IsLaM

dp problem.find the number of ways
Автор RaHuL-IsLaM, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
3 года назад, скрыть # |
← Rev. 5  
Проголосовать: нравится 0 Проголосовать: не нравится

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}$$$

→ Ответить