<prompt> LeetCode inataka kumpa mmoja wa wafanyakazi wake bora chaguo la kusafiri kati ya miji n ili kukusanya matatizo ya algoriti. Lakini kazi yote na hakuna mchezo humfanya Jack kuwa mvulana mwepesi, unaweza kuchukua likizo katika miji na wiki fulani. Kazi yako ni kupanga ratiba ya kusafiri ili kuongeza idadi ya siku za likizo unazoweza kuchukua, lakini kuna sheria na vikwazo fulani unavyohitaji kufuata.Sheria na vikwazo:1. Unaweza tu kusafiri kati ya miji n, inayowakilishwa na faharasa kutoka 0 hadi n - 1. Hapo awali, uko katika jiji lililowekwa alama 0 siku ya Jumatatu.2. Miji imeunganishwa na ndege. Safari za ndege zinawakilishwa kama mpangilio wa n x n sio lazima ulinganifu, unaoitwa ndege zinazowakilisha hali ya shirika la ndege kutoka mji i hadi jiji j. Ikiwa hakuna kukimbia kutoka kwa mji i hadi mji j, ndegeij 0; Vinginevyo, ndegeij 1. Pia, ndegeii 0 kwa i zote.3. Una wiki k kila wiki ina siku saba za kusafiri. Unaweza tu kuchukua safari za ndege mara moja kwa siku na unaweza tu kuchukua safari za ndege kila Jumatatu asubuhi. Kwa kuwa muda wa ndege ni mfupi sana, hatuzingatii athari za muda wa ndege.4. Kwa kila jiji, unaweza tu kuwa na vikwazo vya siku za likizo katika wiki tofauti, ukizingatia mkusanyiko wa n x k unaoitwa siku unaowakilisha uhusiano huu. Kwa thamani ya sikuij, inawakilisha siku za juu zaidi unazoweza kuchukua likizo katika jiji i katika wiki j.5. Unaweza kukaa katika jiji linalozidi idadi ya siku za likizo, lakini unapaswa kufanya kazi kwa siku za ziada, ambazo hazitahesabiwa kuwa siku za likizo.6. Ukisafiri kwa ndege kutoka jiji A hadi jiji B na kuchukua likizo siku hiyo, makato ya siku za likizo yatahesabiwa kuelekea siku za likizo za jiji B katika wiki hiyo.7. Hatuzingatii athari za saa za ndege kwenye hesabu ya siku za likizo.Kwa kuzingatia viwango viwili vya ndege na siku, rudisha _siku za juu zaidi za likizo unazoweza kuchukua katika_ k _wiki_.Mfano wa 1:Ingizo: safari za ndege 0,1,1,1,0,1,1,1,0, siku 1, 3,1,6,0,3,3,3,3Pato: 12Maelezo:Moja ya mikakati bora ni:Wiki ya 1 : kuruka kutoka jiji 0 hadi jiji 1 siku ya Jumatatu, na kucheza siku 6 na kufanya kazi siku 1.Ingawa unaanzia jiji 0, tunaweza pia kuruka hadi na kuanza katika miji mingine kwani ni Jumatatu.Wiki ya 2 : kuruka kutoka mji 1 hadi mji 2 siku ya Jumatatu, na kucheza siku 3 na kufanya kazi siku 4.Wiki ya 3 : kaa katika jiji la 2, na ucheze siku 3 na ufanye kazi siku 4.Jibu 6 3 3 12.Mfano wa 2:Ingizo: safari za ndege 0,0,0,0,0,0,0,0,0, siku 1, 1,1,7,7,7,7,7,7Pato: 3Maelezo:Kwa kuwa hakuna ndege zinazokuwezesha kuhamia jiji lingine, unapaswa kukaa katika jiji 0 kwa wiki 3 zote.Kwa kila wiki, una siku moja tu ya kucheza na siku sita za kufanya kazi.Kwa hivyo idadi ya juu ya siku za likizo ni 3.Jibu 1 1 1 3.Mfano wa 3:Ingizo: safari za ndege 0,1,1,1,0,1,1,1,0, siku 7, 0,0,0,7,0,0,0,7Pato: 21Maelezo:Moja ya mikakati bora ni:Wiki ya 1 : kaa jijini 0, na ucheze siku 7.Wiki ya 2 : kuruka kutoka jiji 0 hadi jiji 1 siku ya Jumatatu, na kucheza siku 7.Wiki ya 3 : kuruka kutoka mji 1 hadi mji 2 siku ya Jumatatu, na kucheza siku 7.Jibu 7 7 7 21Vikwazo: n flights.length n safari za ndegei.urefu n siku.urefu k sikui.urefu 1 n, k 100 ndegeij ama ni 0 au 1. 0 sikuij 7  <response>: def maxSiku zaVacationndege, siku: n lenzi ndege k lenzisiku0 memo -1 k kwa _ katika safun def dfscurrentWeek, currentCity: ikiwa sasaWiki k: kurudi 0 ikiwa ni memocurrentCitycurrentWeek ! -1: rudisha kumbukumbucurrentCitycurrentWeek maxVacation dayscurrentCitycurrentWeek dfscurrentWeek 1, currentCity kwa mimi katika safun: ikiwa safari za ndegecurrentCityi 1: maxVacation maxmaxLikizo, sikuicurrentWeek dfscurrentWeek 1, i memocurrentCitycurrentWeek maxVacation kurudi maxLikizo rudisha dfs0, 0 