Naloga: Trikotnik števil

Iz MaFiRaWiki

Dan je trikotnik števil; v prvi vrstici je eno število, v drugi dve, itd., v zadnji n števil. Mislimo si, da bi začeli v vrhu trikotnika in nato šli vsakič na eno od dveh števil, ki sta pod trenutnim. (Z drugimi besedami: če smo bili prej v j-tem številu i-te vrstice, gremo lahko bodisi na j-to bodisi na (j+1)-vo število (i+1)-ve vrstice.) Ko pridemo do zadnje vrstice, seštejemo vsa obiskana števila. Katera pot po trikotniku nam da največjo vsoto?

Primer

Pot z največjo vsoto v spodnjem trikotnik je 4-7-9, ki nam da vsoto 20.

Rešitev

Osebna orodja