<prompt> Kwa kuzingatia m x n gridi iliyojazwa na nambari zisizo hasi, tafuta njia kutoka juu kushoto hadi kulia chini, ambayo hupunguza jumla ya nambari zote kwenye njia yake.Kumbuka: Unaweza tu kusogea chini au kulia wakati wowote kwa wakati.Mfano wa 1:Ingizo: gridi 1,3,1,1,5,1,4,2,1Pato: 7Maelezo: Kwa sababu njia 1 - 3 - 1 - 1 - 1 inapunguza jumla.Mfano wa 2:Ingizo: gridi 1,2,3,4,5,6Pato: 12Vikwazo: m grid.length n gridi ya taifai.length 1 m, n 200 0 gridiij 100  <response>: chatudef minPathSumgridi: m, n lenigridi, lenigridi0 kwa i katika safu1, m: gridii0 gridii - 10 kwa i katika safu1, n: gridi0i gridi0i - 1 kwa i katika safu1, m: kwa j katika safu1, n: gridiij mingridii - 1j, gridiij - 1 gridi ya kurudisham - 1n - 1maelezoAlgorithm hutatua tatizo kupitia programu yenye nguvu. Inaunda meza na kuijaza kwa sheria zifuatazo:1. Kipengele cha kwanza cha kila safu kitakuwa jumla ya kipengele cha safu mlalo kilichotangulia na thamani yake ya sasa.2. Kipengele cha kwanza cha kila safu kitakuwa jumla ya kipengele chake cha awali cha safu wima na thamani yake ya sasa.3. Kwa vipengele vingine vyote, pata njia ya chini vipengele kutoka juu yake i-1,j na kushoto i,j-1 majirani, na kisha uongeze thamani yake ya sasa.Mwishoni mwa kitanzi, seli ya chini kulia ina jumla ya njia ya chini kutoka kona ya juu kushoto hadi kona ya chini kulia. 