<prompt> Kwa kuzingatia mifuatano miwili neno1 na neno2, rudisha _idadi ya chini zaidi ya utendakazi inayohitajika ili kubadilisha neno1 kuwa neno2_.Una shughuli tatu zifuatazo zinazoruhusiwa kwenye neno: Ingiza mhusika Futa mhusika Badilisha mhusikaMfano wa 1:Ingizo: neno1 farasi, neno2 rosPato: 3Maelezo:farasi - rose badilisha h na rrose - rose ondoa rrose - ros ondoa eMfano wa 2:Ingizo: neno1 nia, neno2 utekelezajiPato: 5Maelezo:nia - kuingiza ondoa tintion - ention badilisha i na eenention - exention badilisha n na xexention - utekelezaji badilisha n na cutekelezaji - utekelezaji ingiza uVikwazo: 0 word1.length, word2.length 500 neno1 na neno2 linajumuisha herufi ndogo za Kiingereza.  <response>: chatudef minDistanceneno1: str, neno2: str - int: m, n lenineno1, lenineno2 dp 0 n 1 kwa _ katika safum 1 kwa mimi katika safu m 1: kwa j katika safun 1: ikiwa mimi 0: dpij j elif j 0: dpij i elif neno1i - 1 neno2j - 1: dpij dpi - 1j - 1 kwingine: dpij mindpi - 1j, dpij - 1, dpi - 1j - 1 1 rudisha dpmnmaelezoAlgorithm inayotumiwa ni programu ya nguvu. Tunaunda dp ya jedwali la 2D na vipimo m1 x n1, ambapo m ni urefu wa neno1 na n ni urefu wa neno2. Kila seli dpij inawakilisha idadi ya chini zaidi ya utendakazi inayohitajika kubadilisha neno10...i-1 hadi neno20...j-1.Kwa kila seli, tuna masharti yafuatayo:1. Iwapo ama i au j ni 0, inamaanisha kuwa moja ya mifuatano haina kitu, kwa hivyo idadi ya chini zaidi ya shughuli zinazohitajika ni urefu wa mfuatano usio tupu i au j.2. Ikiwa herufi za sasa za mifuatano miwili ni sawa neno1i-1 neno2j-1, si lazima tufanye chochote, kwa hivyo dpij dpi -1j-1.3. Ikiwa herufi za sasa ni tofauti, tunachukua kiwango cha chini cha zifuatazo na kuongeza 1: a. dpi-1j: Futa operesheni b. dpij-1: Weka operesheni c. dpi-1j-1: Badilisha operesheniBaada ya kujaza jedwali, idadi ya chini zaidi ya shughuli itakuwa dpmn. 