Nombre de chemins dans une grille

Dans une grille de taille $n×m$, on souhaite compter tous les chemins allant du coin inférieur gauche (au Sud-Ouest) repéré par $(0, 0)$ vers le coin supérieur droit (au Nord-Est) repéré par $(n, m)$.

Un point repéré par la position $(n, m)$ a donc pour coordonnées $(n, m)$ dans un repère ayant pour origine le point situé en bas à gauche de la grille.

Les seuls mouvements autorisés sur la grille sont :

Aller au Nord (↑) d'une unité.
Aller à l'Est (→) d'une unité.

Les chemins pour aller de $(0, 0)$ à $(4, 3)$

Ceux obtenus en venant du sud $(4, 2)$, il y en a 15.

Ceux obtenus en venant de l'Ouest $(3, 3)$, il y en a 20.

Écrire une fonction nb_chemins qui prend en paramètres deux entiers n et m. (n, m) est un tuple donnant une position sur la grille. Cette fonction renvoie le nombre de chemins allant de $(0, 0)$ jusqu'à $(n, m)$.

Pour ce faire, on remarquera :

Si n ou m est nul,
- alors le seul chemin est en ligne droite, la réponse est 1,
sinon :
- n et m sont non nuls et les chemins qui vont en (n, m) se répartissent en deux catégories :
  - ceux qui venaient de (n - 1, m ),
  - ceux qui venaient de (n , m - 1),
On utilisera un dictionnaire pour mémoriser les résultats intermédiaires.

Exemples

>>> nb_chemins(3, 3)
20
>>> nb_chemins(4, 2)
15
>>> nb_chemins(4, 3)
35

Contraintes : Ici, $0\leqslant n \leqslant 20$ et $0\leqslant m \leqslant 20$.

Compléter le code :

Version videVersion à trous

Évaluations restantes : 10/10

.128013uk /xCiOERP)ù=h{-a,1è8n]fI.r6mc;pày72tçl0qsebwS}_L!53(é?êvM:[N4dgU×+9oD050:0S0M0s0h0O0R0d0F0O0s0R0R0o010M0h0H010406050R0b0E0E0s0C0J040V0_0O0b1b0_0x0d020s0E0H0G0d0k0S1l0C0Q0b0S0R050e1i1k1m1o1g0H041M1T051W0e1W1Y1T1g0:0h0*131517190p0h0;0p0O1:0p0M1e050~0T0O0S1+1618011/1;1?1;0M1|1~1`0M0T0_0:1o1{0C1U0M0p131r0R0H0s0x190L01201-010z100S0x1z0S1`2o2q2v222y1~2B0E2D040a0d0l0C0_0H0_0R0h1u1w0|2m0C0C0S0F2Y1M2F0x1U0e2k2.0M2i2h2j0:2H191?0x2A2V1`1(1*14212{0h2}0x2e1)1`0H2%1U2,2.3f1h2p1w332w380C1l0O1e0d0u2+3j1f3i2G3l223n3p3r0L3u2q3w2,2`013B0s3q040d0#3F2-1g3I3z193L3N0d0/3R3H3j3J3X3r0!3#3T3%3V3K0_3o3M3r0D3,3x3k1,3A3;3C3O0K3_3U3|3W3~3?3O0w423.443:3=3Y0^4a3y4c3)040u0P4h3{344d3 0u3t1N3v1V3d1M312;0:2^3J0F2e2N0{1)1U3c0S3e4w4v3G054F0|4N4i4q0x1e0x0T0X0F0p1F360R0X2M0E3#0d3`3J0_1e0o4.4:3/4Z1e1(2)3#4_4c1d040$0m3,063-4V2w0c4|0S0z4 434q0U3r5f4b4W0z4Y4!4$4(0x1L4P2-504q520$5k593A4Y5A4p2w520t4^5g3m1e4-5u4U5F22520m0,3,0d5W4/5K225b040h5e5O5Y5l5G1e5z5O5w5L040x5E3J5H5J5+5C045N3h5Z195S5`5B190_5i5=0_0M635Q6567366b3(5o4#4%0E4)4+1F5@3/525U5O065X6v5*64015#5%6g4`5D5)5:224=040o4@6F60016l1e4n6M5{6d1e3;6C4j5M6X4q6I6K6!2w6P046R5 6T016r5V6w6=6G3W1e2%1i0O0~6a6S6y6$6(226*4u3f6u6=6x6c6z1e0S110S6p511e6s76786w6@3K6_1K0b6|0s6~3f794;4?726^5=5p6k4)7g5x5-7F5;5?6 7a6I0r7z6O0h1e754w6N5_7L6h5}7I5R1e557X3/6I0@7P4X7B6j5r5t6-6y5y7!7A7K7=7a7W7v7n7-5~3v7w7)1e7O7(4c747^6/7$6;6?6N7-4Z7/6l5s6n814Q7V1e0-5.7{7Y7`7U6.7}827 6Z5/8o040m0y7P71874W7p6{6}8d834c5#2%0M0b0C8u3G8O8J7.5q8j4*4,8a528q8a8g8(1e5I8I5;8m5v8C8E3_0e4S4M4x8|0e4A1M0M4C912?2/2d2f2;0s1}8~4A1S5P3J2%0E0X0z0s0c0S0X0p0#1e1E1G1I1K0d7j4O1$1X049s1m1I1v129u0d150d0*1m0h9a1~4/8{8Z7D8k8%8`4G3O1K0M0d0b2}9K9M9O1 0;0O0_0T3M0S0B0d0Y9v0:1v0x0%9v0H0S0C2W0R0M2A9!9_0x0F0da42%9I9^5%0z0%2%0x0M120s0H9~110d0C0%0F8T2W0z0R0B1V3w1T0=3k9T0d2U8T0d3M1~0C0d2!7n9M2k1la30f1e090$0$0P0t0d0P0m097%7v0I8X2waO0paQ0SaS04aU0$0/aY0#a#a%829~1t0d0)2=1 0:ar0C2XaE1m9#9%4$0 9%2!0F1m0s2)0v6`2m1A2V9|aL1 0/9Q9X000j001M9Ra99!0#bs4T000.bw9W4Tax1Zaz040lb8a/1F0H1~aY4R9X010j0j0.bYbZ01bx9XaLb4b6050s3J9,1@2c0_aSaL7t0s0r0M0J9~190h1l0;2Db@0~0r0U0h0:2k190s1t4=c3b_4%b:cacc2u0p2%0z1.280H0R0,0ebHa/0B0z3;c10Balcq0B0S0:0bbf2Ycw0C0e2y4$0h9 0R0ebP0C0F0h0F1K0e8h8!6m0;b50O1~cR0f0_0X4!0k0j0+0eb 0sc1cQc!0x0X0u0w0B0R0*0;2u0:b^0r0|0R0F0r2U2W2Y192d280_0E1`b 0;aH6|192u0RcTco0Mcqcscu0fcwcy9;cBawcEcG7t0h1vcJcLcV1/cPc*9 cUcWcQcZ9T4*c$10c)a/c,c.c:c=c0cXc`c|c~d0d22.0s2.9z1T0A0O0d0JaHaH1t2qa51 c`12aFaKaI9 bpa*22a,a.a:a=aXaZa`4.a)aNb5aP7ta/aTaVa@3Pef5)9Hbe0pbc9^d bgbibk4Fbm0R9|122!brbUbDbvb%4Tbz3PbC4MbEbG9RbJd;040gdh2Maiac12eC0Ha3aK0(ay1g7r3w1?04d?d^d`ei2Xa-eleba?0@bB0o0d0Ka$4.bf0Cbh0Mbj1KbJe;1ge;e?d_b-e_ekaRen0/f45)4$0_0h0faE2V2W9be11m6le$f2aE15dQfuaGbRbhe51~12eJeReLcu04fc0he:fT0j5s0b2X0SaYfLeQ04eSeM4MaEah379!f$bBfIfF6`0~ai1KaY0R2qak0*fraK9PfqfsaY2!1l0x0hfab90h9ufS3w0ee/9e9@0d380E0Tabeu7:fGe3c(e5aM6Ne9e|enaWaYa!foa(e7caeje{fla;eoa^er7v9Zacgkdhgnb21 9k0N9Fe6g32WaKbrf=9}fz0hf2eVbL0`1 g7g9ab0;0%9{f7bSgQglgTgZdTgrdmaJe6fjgIemgKgAeegD82ehgwgHeagz0xaY0EgN82gP9Pg}gogV0sgX5sg frg#gF01gxgJaU0xhb8Wg(fy3og+h5hggK0x0@0EhE2-g-9efW2mate6aQ0p0%aQgc1J0RaY1vaE0Sa~f 0haK9HcWgRgmabgP6s9z313JhAh7090-090T36dh0qhN0E0Wi60W0df1090:0zf70F0q0$i70m0Zi90x0Z0Ein098F8 4J9e0i0n9we-05gh05e;hKgyhM0Zic3s0?0L0?0#0?090F9_aj0?ik0r0u0m0?hDa{4Q0efdiEfTiGhB0$iriK0uiMiOiQiS690RiV0EiXiZhPi$5vi(fTfei+hee`hLa=iliJf1i;iNiPiRiTi`ikhOi}iVilhQ2.i)gg0ObLbNaKbP1AbSiBiDiFj6fkh a?jbiLje0?fnj0jpj3i*9f3/h~e}0#jGjdiOjo1Mi)jB6.jRgz0/e imi:i=iP0/0?0!0?0D0?f3jLjYjNjr3wh|jQhfiHi0i2i40E0qj(0#i90/ibidifih0qjVj-j/j;j?i9kfjJ091I0s2_0?0dkn0bkpjHiOkakskcbh0qj:j=0Kkkj,kyieigkBj:iR2qcW0O0q0D0Wkjkei@kO7d0qje0Wky0#0!it4ziw4z0}0 1104.

Évaluations restantes : 10/10

.128013uk /xCiOERP)ù=h{-a,1è8n]fI.r6mc;pày72tçl0qsebwS}_L!53(é?êvM:[N4dgU×+9oD050:0S0M0s0h0O0R0d0F0O0s0R0R0o010M0h0H010406050R0b0E0E0s0C0J040V0_0O0b1b0_0x0d020s0E0H0G0d0k0S1l0C0Q0b0S0R050e1i1k1m1o1g0H041M1T051W0e1W1Y1T1g0:0h0*131517190p0h0;0p0O1:0p0M1e050~0T0O0S1+1618011/1;1?1;0M1|1~1`0M0T0_0:1o1{0C1U0M0p131r0R0H0s0x190L01201-010z100S0x1z0S1`2o2q2v222y1~2B0E2D040a0d0l0C0_0H0_0R0h1u1w0|2m0C0C0S0F2Y1M2F0x1U0e2k2.0M2i2h2j0:2H191?0x2A2V1`1(1*14212{0h2}0x2e1)1`0H2%1U2,2.3f1h2p1w332w380C1l0O1e0d0u2+3j1f3i2G3l223n3p3r0L3u2q3w2,2`013B0s3q040d0#3F2-1g3I3z193L3N0d0/3R3H3j3J3X3r0!3#3T3%3V3K0_3o3M3r0D3,3x3k1,3A3;3C3O0K3_3U3|3W3~3?3O0w423.443:3=3Y0^4a3y4c3)040u0P4h3{344d3 0u3t1N3v1V3d1M312;0:2^3J0F2e2N0{1)1U3c0S3e4w4v3G054F0|4N4i4q0x1e0x0T0X0F0p1F360R0X2M0E3#0d3`3J0_1e0o4.4:3/4Z1e1(2)3#4_4c1d040$0m3,063-4V2w0c4|0S0z4 434q0U3r5f4b4W0z4Y4!4$4(0x1L4P2-504q520$5k593A4Y5A4p2w520t4^5g3m1e4-5u4U5F22520m0,3,0d5W4/5K225b040h5e5O5Y5l5G1e5z5O5w5L040x5E3J5H5J5+5C045N3h5Z195S5`5B190_5i5=0_0M635Q6567366b3(5o4#4%0E4)4+1F5@3/525U5O065X6v5*64015#5%6g4`5D5)5:224=040o4@6F60016l1e4n6M5{6d1e3;6C4j5M6X4q6I6K6!2w6P046R5 6T016r5V6w6=6G3W1e2%1i0O0~6a6S6y6$6(226*4u3f6u6=6x6c6z1e0S110S6p511e6s76786w6@3K6_1K0b6|0s6~3f794;4?726^5=5p6k4)7g5x5-7F5;5?6 7a6I0r7z6O0h1e754w6N5_7L6h5}7I5R1e557X3/6I0@7P4X7B6j5r5t6-6y5y7!7A7K7=7a7W7v7n7-5~3v7w7)1e7O7(4c747^6/7$6;6?6N7-4Z7/6l5s6n814Q7V1e0-5.7{7Y7`7U6.7}827 6Z5/8o040m0y7P71874W7p6{6}8d834c5#2%0M0b0C8u3G8O8J7.5q8j4*4,8a528q8a8g8(1e5I8I5;8m5v8C8E3_0e4S4M4x8|0e4A1M0M4C912?2/2d2f2;0s1}8~4A1S5P3J2%0E0X0z0s0c0S0X0p0#1e1E1G1I1K0d7j4O1$1X049s1m1I1v129u0d150d0*1m0h9a1~4/8{8Z7D8k8%8`4G3O1K0M0d0b2}9K9M9O1 0;0O0_0T3M0S0B0d0Y9v0:1v0x0%9v0H0S0C2W0R0M2A9!9_0x0F0da42%9I9^5%0z0%2%0x0M120s0H9~110d0C0%0F8T2W0z0R0B1V3w1T0=3k9T0d2U8T0d3M1~0C0d2!7n9M2k1la30f1e090$0$0P0t0d0P0m097%7v0I8X2waO0paQ0SaS04aU0$0/aY0#a#a%829~1t0d0)2=1 0:ar0C2XaE1m9#9%4$0 9%2!0F1m0s2)0v6`2m1A2V9|aL1 0/9Q9X000j001M9Ra99!0#bs4T000.bw9W4Tax1Zaz040lb8a/1F0H1~aY4R9X010j0j0.bYbZ01bx9XaLb4b6050s3J9,1@2c0_aSaL7t0s0r0M0J9~190h1l0;2Db@0~0r0U0h0:2k190s1t4=c3b_4%b:cacc2u0p2%0z1.280H0R0,0ebHa/0B0z3;c10Balcq0B0S0:0bbf2Ycw0C0e2y4$0h9 0R0ebP0C0F0h0F1K0e8h8!6m0;b50O1~cR0f0_0X0s0X0k0j0+0eb 0sc1cQc!0x0X0u0w0B0R0*0;2u0:b^0r0|0R0F0r2U2W2Y192d280_0E1`b 0;aH6|192u0RcTco0Mcqcscu0fcwcy9;cBawcEcG7t0h1vcJcLcV1/cPc*9 cUcWcQcZ9T4*c$10c)a/c,c.c:c=c@c_8`9Tc}c d1d32.0s2.9z1T0A0O0d0JaHaH1t2qa51 c{12aFaKaI9 bpa*22a,a.a:a=aXaZa`4.a)aNb5aP7ta/aTaVa@3Peh5)9Hbe0pbc9^e1bgbibk4Fbm0R9|122!brbUbDbvb%4Tbz3PbC4MbEbG9RbJd?040gdi2Maiac12eE0Ha3aK0(ay1g7r3w1?04d^d`d|ek2Xa-eneda?0@bB0o0d0Ka$4.bf0Cbh0Mbj1KbJe?1ge?e^d{b-e{emaRep0/f65)4$0_0h0faE2V2W9be31m6le(f4aE15dRfwaGbRbhe71~12eLeTeNcu04fe0he=fV0j5s0b2X0SaYfNeS04eUeO4MaEah379!f(bBfKfH6`0~ai1KaY0R2qak0*ftaK9PfsfuaY2!1l0x0hfcb90h9ufU3w0ee;9e9@0d380E0Tabew7:fIe5c(e7aM6Nebe~epaWaYa!fqa(e9caele}fna;eqa^et7v9Zacgmdigpb21 9k0N9Fe8g52WaKbrf@9}fB0hf4eXbL0`1 g9gbab0;0%9{f9bSgSgngVg#dUgtdnaJe8flgKeogMgCeggF82ejgygJecgB0xaY0EgP82gR9Pg gqgX0sgZ5sh1ftg%gH01gzgLaU0xhd8Wg*fA3og-h7higM0x0@0EhG2-g/9efY2mate8aQ0p0%aQge1J0RaY1vaE0Sa~g10haK9HcWgTgoabgR6s9z313JhCh9090-090T36di0qhP0E0Wi80W0df3090:0zf90F0q0$i90m0Zib0x0Z0Eip098F8 4J9e0i0n9we/05gj05e?hMgAhO0Zie3s0?0L0?0#0?090F9_aj0?im0r0u0m0?hFa{4Q0effiGfViIhD0$itiM0uiOiQiSiU690RiX0EiZi#hRi(5vi*fVfgi-hge|hNa=iniLf3i?iPiRiTiVi|imhQi iXinhS2.i+gi0ObLbNaKbP1AbSiDiFiHj8fmi1a?jdiNjg0?fpj2jrj5i,9f3/i0e 0#jIjfiQjq1Mi+jD6.jTgB0/f1ioi=i@iR0/0?0!0?0D0?f5jNj!jPjt3wh~jShhiJi2i4i60E0qj*0#ib0/idifihij0qjXj/j;j?j^ibkhjL091I0s2_0?0dkp0bkrjJiQkckukebh0qj=j@0Kkmj.kAigiikDj=iT2qcW0O0q0D0Wklkgi_kQ7d0qjg0WkA0#0!iv4ziy4z0}0 1104.