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.

Auto comment: topic has been updated by LegendRanger (previous revision, new revision, compare).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}$$$

good solution but still confuse?