Scala con un costo per gradino

Una scala ha 9 gradini, numerati da 1 a 9. Chi sale paga il costo di ogni gradino su cui posa il piede; i costi, dal gradino 1 al gradino 9, sono:

4, 1, 5, 6, 2, 7, 3, 3, 6

Si parte dal pavimento e a ogni passo si sale di 1 o di 2 gradini; anche il gradino 9 si paga. Qual è il costo minimo per arrivare in cima?