[Zagadka] Autobusy & pomysł na algorytm

Witam.
Nie mam pojecia jaki algorytm do rozwiazania tego obrac:

Pewna jednokierunkowa ulica posiada przystanek autobusowy co kilometr. Pasażer ponosi opłatę stosowną do liczby kilometrów przebytych autobusem. Przykładowa lista opłat jest ukazana w tabeli poniżej.
Kilometry 1 2 3 4 5 6 7 8 9 10
Cena 12 21 31 40 49 58 69 79 90 101
Żaden z autobusów nie pokonuje więcej niż 10 kilometrów. Pasażer chce przejechać n kilometrów, gdzie 1 < n < 100. Jeżeli przyjmiemy, że aby ukończyć podróż pasażer może jechać dowolną ilość razy, który wybór kursów zapewni mu minimalną opłatę całkowitą ?

Zauważ, że opłaty nie koniecznie mają sens w wymiarze ekonomicznym. Na przykład, możliwe, że opłata za 10 km jest mniejsza niż ta za 1km.

W skrocie: chce przejechac 14km i moge jechac sobie 2x2km 3x3km i 1x1km, jesli tylko daloby to minimalna oplate. Tabela oplat nie jest statyczna i bedzie ja sie podawalo na starcie programu. Sprawdzanie wszystkich kombinacji zdecydowanie odpada. Tak wiec ma ktos jakis pomysl na algorytm?

Tak na szybko - nie wiem czy to będzie dobrze, ale wydaje mi się, że:

Na początku posortować tabelę opłat według ceny za kilometr (najpierw taka odległość, w której cena jednego kilometra wyjdzie najtaniej, potem następna etc).
Potem Przejechać maksymalną ilość odcinków za pomocą tej odległości i to co nam zostanie dalej dobierać zgodnie z posortowaną tabelą i pozostałymi do przejechania kilometrami.

Dla podanego przez Ciebie przykładu będzie to: 2x6km, 1x2km co da w sumie 137 (zł ?)

Tabela będzie wyglądać:

6 km - 9,67 zł/km
5 km - 9,8 zł/km
7 km - 9,85 zł/km
8 km - 9,875 zł/km
4 km oraz 9 km - 10 zł/km
10 km - 10,1 zł/km
3 km - 10,33 zł/km
2 km - 10,5 zł/km
1 km - 12 zł/km
(pogrubienia miały sprawić, że będzie bardziej czytelne - ale chyba nie wyszło ;) )

Algorytm identyczny w zasadzie z dobieraniem minimalnej ilości monet/banknotów w celu uzyskania pożądanej kwoty.

Ale mogę się mylić...

Tak tez myslalem na poczatku, jednak to na pewno nie to, gdyz np jak mamy do przejechania 21km i powiedzmy ze najtaniej za km wychodzi jechac po 4km to mamy 5x4km i teraz dodajemy powiedzmy ten 1km, jednak on moze kosztowac 100x wiecej niz cala dotychczasowa droga. W takim wypadku mozna by tez odjac jeden w ilosci 'tych najtanszych' i probowac dobierac tak by pasowaly... jednak co jesli inne 'pasujace'? okaza sie tez abstrakcyjnie wysokie? A powiedzmy ze wystarczylo jechac 3x7km co przeliczajac na cene za kilometr nie jest najtansze tylko gdzies w srodku. Owszem mozna by dojsc do tego odpowiednio podstawiajac w sposob jaki mowisz, jednak dalej jest to metoda w ktorej sprawdzamy wiele kombinacji, tylko nie po kolei ale wg jakiegos schematu. Mi raczej chodzi o konkretne rozwiazanie :)

Banał :)

1. określasz, ile zapłacisz za przjechanie 1km - jest tylko jedna możliwość
2. dla i = 2 -> ilośc_kilometrów sprawdzasz, która z liczb jest najmniejsza:
   (przejechanie i kilometrów za jednym razem),
   (przejechanie i-1 kilometrów za jednym razem) + (przejechanie 1 km)
   (i-2 km) + (2 km)
   ....
   (1 km) + (i - 1) km

I przyjmujesz tą wartość za nową cenę przejechania i kilometrów.