<prompt> Tunacheza Mchezo wa Kubahatisha. Mchezo utafanya kazi kama ifuatavyo:1. Ninachagua nambari kati ya 1 na n.2. Unakisia nambari.3. Ukikisia nambari sahihi, unashinda mchezo.4. Ukikisia nambari isiyo sahihi, basi nitakuambia ikiwa nambari niliyochagua ni juu au chini, na utaendelea kubahatisha.5. Kila wakati unapokisia nambari isiyo sahihi x, utalipa dola x. Ukikosa pesa, unapoteza mchezo.Kwa kuzingatia n fulani, rudisha _kiasi cha chini kabisa cha pesa unachohitaji ili kuhakikishia ushindi bila kujali nitachagua nambari gani_.Mfano wa 1:Ingizo: n 10Pato: 16Maelezo: Mkakati wa ushindi ni kama ifuatavyo:- Masafa ni 1,10. Nadhani 7. - Ikiwa hii ni nambari yangu, jumla yako ni 0. Vinginevyo, unalipa 7. - Ikiwa nambari yangu ni kubwa zaidi, masafa ni 8,10. Nadhani 9. - Ikiwa hii ni nambari yangu, jumla yako ni 7. Vinginevyo, unalipa 9. - Ikiwa nambari yangu ni kubwa zaidi, lazima iwe 10. Nadhani 10. Jumla yako ni 7 9 16. - Ikiwa nambari yangu ni ya chini, lazima iwe 8. Nadhani 8. Jumla yako ni 7 9 16. - Ikiwa nambari yangu ni ya chini, safu ni 1,6. Nadhani 3. - Ikiwa hii ni nambari yangu, jumla yako ni 7. Vinginevyo, unalipa 3. - Ikiwa nambari yangu ni kubwa zaidi, safu ni 4,6. Nadhani 5. - Ikiwa hii ni nambari yangu, jumla yako ni 7 3 10. Vinginevyo, unalipa 5. - Ikiwa nambari yangu ni kubwa zaidi, lazima iwe 6. Nadhani 6. Jumla yako ni 7 3 5 15. - Ikiwa nambari yangu ni ya chini, lazima iwe 4. Nadhani 4. Jumla yako ni 7 3 5 15. - Ikiwa nambari yangu ni ya chini, safu ni 1,2. Nadhani 1. - Ikiwa hii ni nambari yangu, jumla yako ni 7 3 10. Vinginevyo, unalipa 1. - Ikiwa nambari yangu ni kubwa zaidi, lazima iwe 2. Nadhani 2. Jumla yako ni 7 3 1 11.Hali mbaya zaidi katika hali hizi zote ni kwamba unalipa 16. Kwa hivyo, unahitaji 16 pekee ili kuhakikisha ushindi.Mfano wa 2:Ingizo: n 1Pato: 0Maelezo: Kuna nambari moja tu inayowezekana, kwa hivyo unaweza kukisia 1 na sio lazima ulipe chochote.Mfano wa 3:Ingizo: n 2Pato: 1Maelezo: Kuna nambari mbili zinazowezekana, 1 na 2.- Nadhani 1. - Ikiwa hii ni nambari yangu, jumla yako ni 0. Vinginevyo, unalipa 1. - Ikiwa nambari yangu ni kubwa zaidi, lazima iwe 2. Nadhani 2. Jumla yako ni 1.Hali mbaya zaidi ni kwamba unalipa 1.Vikwazo: 1 n 200  <response>: chatudef getMoneyAmountn: int - int: dp 0 n 1 kwa _ masafan 1 kwa i katika safu n - 1, 0, -1: kwa j katika safu i 1, n 1: min_cost kueleainf kwa k katika safui, j: gharama k maxdpik - 1, dpk 1j min_cost minmin_cost, gharama dpij min_cost rudisha dp1nmaelezoKanuni hutumia programu inayobadilika ili kupata gharama ya chini inayohitajika ili kuhakikisha ushindi. Tunaunda safu ya 2D dp ambapo dpij inawakilisha gharama ya chini inayohitajika kukisia nambari sahihi kutoka kwa nambari kati ya i na j zikijumlishwa.Tunajaza safu hii kutoka kona ya chini ya kulia, na kuelekea kona ya juu kushoto. Kwa kila thamani ya i na j, tunakokotoa gharama kwa kubahatisha nambari k kati ya i na j. Gharama ni sawa na k maxdpik-1, dpk1j, ambayo ina maana kwamba tunalipa k na kuchukua hali mbaya zaidi, na sisi jaribu kupunguza gharama hii.Baada ya kujaza safu ya dp, gharama ya chini inayohitajika kushinda mchezo unapokisia nambari kutoka 1 hadi n huhifadhiwa katika dp1n. 