<prompt> Kwa kuzingatia nambari kamili za m x n matrix, rudisha _urefu wa njia ndefu zaidi inayoongezeka katika_ matrix.Kutoka kwa kila seli, unaweza kusonga katika pande nne: kushoto, kulia, juu au chini. Huenda usisogeze kimshazari au kusogeza nje ya mpaka yaani, kuzunguka hakuruhusiwi.Mfano wa 1:Ingizo: matrix 9,9,4,6,6,8,2,1,1Pato: 4Maelezo: Njia ndefu zaidi inayoongezeka ni 1, 2, 6, 9.Mfano wa 2:Ingizo: matrix 3,4,5,3,2,6,2,2,1Pato: 4Maelezo: Njia ndefu zaidi inayoongezeka ni 3, 4, 5, 6. Kusonga kwa diagonal hairuhusiwi.Mfano wa 3:Ingizo: matrix 1Pato: 1Vikwazo: m matrix.length n matrixi.urefu 1 m, n 200 0 matrixij 231 - 1  <response>: chatudx 0, 0, 1, -1dy 1, -1, 0, 0def dfsmatrix, memo, i, j: ikiwa kumbukumbuij ! 0: rudisha memoij max_len 0 kwa k katika safu4: ni, nj i dxk, j dyk ikiwa 0 ni lenmatrix na 0 nj lenmatrix0 na matrixninj matrixij: max_len maxmax_len, dfsmatrix, memo, ni, nj memoij max_len 1 rudisha memoijdef longest_increasing_pathmatrix: m, n lenimatrix, lenimatrix0 memo 0 n kwa _ masafam zaidi 0 kwa mimi katika safum: kwa j katika safun: ans maxans, dfsmatrix, memo, i, j kurudi ansmaelezoTunatumia utafutaji wa kina-kwanza DFS kuchunguza gridi ya taifa. Wazo la msingi ni kuanza kutoka kwa kila seli na kusonga katika pande nne zinazoruhusiwa kushoto, kulia, juu na chini. Tunaweza tu kuhamia kisanduku cha jirani ikiwa thamani katika seli hiyo ni kubwa kuliko kisanduku cha sasa njia inayoongezeka.Tunatumia kukariri kuhifadhi njia ndefu zaidi inayoongezeka kuanzia kila seli ili kuepuka hesabu zisizo na maana. Kwa kila seli i, j, tunaita chaguo za kukokotoa za DFS na kukokotoa njia ndefu zaidi inayoongezeka kuanzia kisanduku hicho kwa kuchunguza seli jirani katika pande zote nne.Hatimaye, tunarudisha njia ndefu zaidi inayoongezeka inayopatikana kwenye gridi ya taifa.Utata wa saa wa algoriti hii ni Om n tunapotembelea kila seli mara moja, ambapo m ni idadi ya safu mlalo na n ni idadi ya safu wima katika mkusanyiko uliotolewa. 