Блог пользователя LegendRanger

dp problem.find the number of ways
Автор LegendRanger, история, 7 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
7 месяцев назад, # |
← 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}$$$

→ Ответить