<prompt> Unapewa maputo n, yaliyowekwa faharasa kutoka 0 hadi n - 1. Kila puto imepakwa rangi na nambari inayowakilishwa na safu nums. Unaulizwa kupasua puto zote.Ukipasua puto ya ith, utapata sarafu za numsi - 1 numsi numsi 1. Ikiwa i - 1 au i 1 itatoka nje ya mipaka ya safu, basi ichukue kana kwamba kuna puto iliyopakwa 1 juu yake.Rudisha _sarafu nyingi unazoweza kukusanya kwa kupasua puto kwa busara_.Mfano wa 1:Ingizo: nambari 3,1,5,8Pato: 167Maelezo:nambari 3,1,5,8 -- 3,5,8 -- 3,8 -- 8 -- sarafu 315 358 138 181 167Mfano wa 2:Ingizo: nambari 1,5Pato: 10Vikwazo: n nums.length 1 n 300 0 numsi 100  <response>: chatudef maxCoinsnambari: nambari 1 nambari 1 n lenzi nambari dp 0 n kwa _ masafan kwa urefu katika safu1, n - 1: kwa masafa ya kushoto 1, n - urefu: kulia kushoto urefu - 1 kwa mimi katika anuwai kushoto, kulia 1: dpkushotokulia maxdpkushotokulia, numskushoto - 1 numsi numskulia 1 dpkushotoi - 1 dpi 1kulia rudisha dp1n - 2maelezoTatizo hili linaweza kutatuliwa kwa kutumia programu yenye nguvu. Tunafafanua safu ya 2D dp ambapo dpkushotokulia inawakilisha kiwango cha juu zaidi cha sarafu tunachoweza kupata kwa kupasua puto kutoka faharasa kushoto hadi kulia. Ili kujaza dp, tunarudia safu ndogo zote zinazowezekana kwa kutofautiana urefu na kukokotoa suluhu mojawapo kwa kila safu ndogo kwa kuchagua mpangilio wa kupasuka. Kwa kila safu ndogo, tunarudia puto zote, na kupasua puto ith na kuchukua thamani ya juu kati ya dpkushotokulia ya sasa na sarafu zilizopatikana kwa kupasua ith puto sarafu zilizopatikana. kwa kupasua puto upande wa kushoto wa puto ith sarafu zilizopatikana kwa kupasua puto zilizo upande wa kulia wa puto ith. Hatimaye, tunarudisha dp1n - 2 kwa kuwa tuliongeza puto dumu zenye thamani 1 mwanzoni na mwisho. 