You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
notes/classes/algorithms/coin_row_problem.md

749 B

coin row problem

from algorithms

given a row of n coins whose values are positive integers, we want to maximise the total without taking adjacent coins

Index Coin Max
0 - -
1 3 3
2 6 6
3 8 11 (3&8)
4 4 11
5 1 12 (3,8,&1)
6 2 13 (3,8,&2)
7 4 16 (3,8,1,&4)
8 5 18 (3,8,2,&5)

The function we can use to reason this is

$$ F(n) = max(index + F(n-2), F(n-1)) $$ given that n>1, f(0) = 0, and f(1) = index(1)

see also

list without id file.inlinks
where file.name = this.file.name