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

.128013àç[3ùè.4ênx/R8p)IL0EhCDv72c56g9Nf=buS-,_×l(w?OaPké;:ors1qm!yd]i{ U}te+050-0^0@0V0/0Q0%0;0B0Q0V0%0%0I010@0/0p010406050%0K0*0*0V0$0,040L0#0Q0K1a0#0k0;020V0*0p0Z0;0n0^1k0$0)0K0^0%050m1h1j1l1n1f0p041L1S051V0m1V1X1S1f0-0/0y121416180v0/0E0v0Q1/0v0@1d050}0J0Q0^1*1517011.1:1=1:0@1{1}1_0@0J0#0-1n1`0$1T0@0v121q0%0p0V0k180A011 1,010H0 0^0k1y0^1_2n2p2u212x1}2A0*2C040a0;0W0$0#0p0#0%0/1t1v0{2l0$0$0^0B2X1L2E0k1T0m2j2-0@2h2g2i0-2G181=0k2z2U1_1%1)13202`0/2|0k2d1(1_0p2$1T2+2-3e1g2o1v322v370$1k0Q1d0;0(2*3i1e3h2F3k213m3o3q0A3t2p3v2+2_013A0V3p040;0e3E2,1f3H3y183K3M0;0i3Q3G3i3I3W3q0C3!3S3$3U3J0#3n3L3q0D3+3w3j1+3z3:3B3N0z3^3T3{3V3}3=3N0o413-433/3;3X0F493x4b3(040(0t4g3`334c3~0(3s1M3u1U3c1L302:0-2@3I0B2d2M0`1(1T3b0^3d4v4u3F054E0{4M4h4p0k1d0k0J0O0B0v1E350%0O2L0*3!0;3_3I0#1d0I4-4/3.4Y1d1%2(3!4^4b1c040R0q3+063,4U2v0X4{0^0H4~424p0S3q5e4a4V0H4X4Z4#4%0k1K4O2,4 4p510R5j583z4X5z4o2v510N4@5f3l1d4,5t4T5E21510q0!3+0;5V4.5J215a040/5d5N5X5k5F1d5y5N5v5K040k5D3I5G5I5*5B045M3g5Y185R5_5A180#5h5;0#0@625P6466356a3%5n4!4$0*4(4*1E5?3.515T5N065W6u5)63015!5$6f4_5C5(5/214;040I4?6E5 016k1d4m6L5`6c1d3:6B4i5L6W4p6H6J6Z2v6O046Q5~6S016q5U6v6;6F3V1d2$1h0Q0}696R6x6#6%216)4t3e6t6;6w6b6y1d0^100^6o501d6r75776v6?3J6^1J0K6{0V6}3e784:4=716@5;5o6j4(7f5w5,7E5:5=6~796H0M7y6N0/1d744v6M5^7K6g5|7H5Q1d547W3.6H0_7O4W7A6i5q5s6,6x5x7Z7z7J7;797V7u7m7,5}3u7v7(1d7N7%4b737@6.7#6:6=6M7,4Y7.6k5r6m804P7U1d0d5-7`7X7_7T6-7|817~6Y5.8n040q0.7O70864V7o6`6|8c824b5!2$0@0K0$8t3F8N8I7-5p8i4)4+89518p898f8%1d5H8H5:8l5u8B8D3^0m4R4L4w8{0m4z1L0@4B902=2.2c2e2:0V1|8}4z1R5O3I2$0*0O0H0V0X0^0O0v0e1d1D1F1H1J0;7i4N1#1W049r1l1H1u119t0;140;0y1l0/991}4.8`8Y7C8j8$8_4F3N1J0@0;0K2|9J9L9N1~0E0Q0#0J3L0^0h0;0s9u0-1u0k0Y9u0p0^0$2V0%0@2z9Z9^0k0B0;a32$9H9@5$0H0Y2$0k0@110V0p9}100;0$0Y0B8S2V0H0%0h1U3v1S0=3j9S0;2T8S0;3L1}0$0;2Z7m9L2j1ka20l1d090R0R0t0N0;0t0q097$7u0b8W2vaN0vaP0^aR04aT0R0iaX0ea!a$819}1s0;0j2;1~0-aq0$2WaD1l9!9$4#0~9$2Z0B1l0V2(0g6_2l1z2U9{aK1~0i9P9W000u001L9Qa89Z0ebr4S000Gbv9V4Saw1Yay040Wb7a.1E0p1}aX4Q9W010u0u0GbXbY01bw9WaKb3b5050V3I9+1?2b0#aRaK7s0V0M0@0,9}180/1k0E2Cb?0}0M0S0/0-2j180V1s4;c2b^4$b/c9cb2t0v2$0Hb}b 1J8_9S0O0(0o0h0%0y0E2t0-b@0M0{0%0B0M2T2V2X182c270#0*1_b~0EaG6{182t0%0$0Bcn0Vc00%cq5qcscucwcy2-0V2-9y1S0r0Q0;0,aGaG1s2pa41~8Z4(aD0#aFaH9~boa)21a+a-a/a;aWaYa_4-a(aMb4aO7sa.aSaUa?3Odf5(9Gbd0vbb9@c~bfbhbj4Ebl0%9{112ZbqbTbCbub$4Sby3ObB4LbDbF9QbIc:040wcN2Lahab11dC0pa2aJ0Tax1f7q3v1=04c=c@c_di2Wa,dldba=0_bA0I0;0za#4-be0$bg0@bi1JbId;1fd;d?c^b,d_dkaQdn0ie45(4#0#0/0ld1160/9a112o3n0/d$e2aD140B9|d2aJbQbgd51}11dJdRdLbG4Lec0/d:eV0u5r0K2W0^aXeNdQ04dSdM4LaDag369Ze(bAeKeG116_0}ah1JaX0%2paj0yeraJ9OeqesaX2Z1k0k0/eab80/9teU3v0md/9d9?0;370*0Jaadu7/d1d30QaId6ejd{ela:aUddaZeoa%d7c9djfAdmfCa=a@dr7u9YabfncNfqb11~9j0c9Ed6f62VaJbqe@9|1l6ke2dVbK0x1~fafcaa0E0Y9`e7bRfTfofWf$9SeyeIcSfxaL6Md9d|dnaVaXfFa`8Vdhg9fKdagc0kaX0*fQ81fS9Og0frfY0Vf!5rg2erf(fI01gafBaT0kfGa{eFf,eAgDgFfMgH0_0*gJ3Ff:9deY2lasd6aP0v0YaPff1I0%aX1uaD0^a}f20/aJ9GeGfUfpaafS6r9y303IgPdb0d090J35cN0:0kgS0?h90?0;e1090-0He70B0:0Rhagp0+hc0k0+0*hq098E8~4I9d0U0f9vd-05fk05d;fzglfChshf3r0P0A0P0e0P090B9^ai0Phn0M0(0q0PgIgg5u0medhHeVhJgbfChuhN0(hPhRhThV680%hY0*h!h$gTh)2-h,hIgjd`hKa;ho0q0+h?h^hShUhWh}hngSi0hYibgUh*h,fj0QbKbMaJbO1zbRhEhGi66-h2emide1h@hQhSeni31Li5h.i7ekgQ0R0eiGhOiJipi4eVeeiPiDgkh:a;0id icieiJ0P0i0P0C0P0D0Pe3iMh+i!1LhGh03.iEa:h4h6fo0:i+0ehc0ihehghihk0:iIh_i;i?i^0zhcjhiK091H0V2^0P0;jq0KjsiWhRjcjvjebg0:jki_jnifjBhhhjjEi?hU2peG0Q0:0D0?jHjgh`jQ7c0:iJ0?jB0e0Chw4yhz4y0|0~1004.

Évaluations restantes : 10/10

.128013àç[3ùè.4ênx/R8p)IL0EhCDv72c56g9Nf=buS-,_×l(w?OaPké;:ors1qm!yd]i{ U}te+050-0^0@0V0/0Q0%0;0B0Q0V0%0%0I010@0/0p010406050%0K0*0*0V0$0,040L0#0Q0K1a0#0k0;020V0*0p0Z0;0n0^1k0$0)0K0^0%050m1h1j1l1n1f0p041L1S051V0m1V1X1S1f0-0/0y121416180v0/0E0v0Q1/0v0@1d050}0J0Q0^1*1517011.1:1=1:0@1{1}1_0@0J0#0-1n1`0$1T0@0v121q0%0p0V0k180A011 1,010H0 0^0k1y0^1_2n2p2u212x1}2A0*2C040a0;0W0$0#0p0#0%0/1t1v0{2l0$0$0^0B2X1L2E0k1T0m2j2-0@2h2g2i0-2G181=0k2z2U1_1%1)13202`0/2|0k2d1(1_0p2$1T2+2-3e1g2o1v322v370$1k0Q1d0;0(2*3i1e3h2F3k213m3o3q0A3t2p3v2+2_013A0V3p040;0e3E2,1f3H3y183K3M0;0i3Q3G3i3I3W3q0C3!3S3$3U3J0#3n3L3q0D3+3w3j1+3z3:3B3N0z3^3T3{3V3}3=3N0o413-433/3;3X0F493x4b3(040(0t4g3`334c3~0(3s1M3u1U3c1L302:0-2@3I0B2d2M0`1(1T3b0^3d4v4u3F054E0{4M4h4p0k1d0k0J0O0B0v1E350%0O2L0*3!0;3_3I0#1d0I4-4/3.4Y1d1%2(3!4^4b1c040R0q3+063,4U2v0X4{0^0H4~424p0S3q5e4a4V0H4X4Z4#4%0k1K4O2,4 4p510R5j583z4X5z4o2v510N4@5f3l1d4,5t4T5E21510q0!3+0;5V4.5J215a040/5d5N5X5k5F1d5y5N5v5K040k5D3I5G5I5*5B045M3g5Y185R5_5A180#5h5;0#0@625P6466356a3%5n4!4$0*4(4*1E5?3.515T5N065W6u5)63015!5$6f4_5C5(5/214;040I4?6E5 016k1d4m6L5`6c1d3:6B4i5L6W4p6H6J6Z2v6O046Q5~6S016q5U6v6;6F3V1d2$1h0Q0}696R6x6#6%216)4t3e6t6;6w6b6y1d0^100^6o501d6r75776v6?3J6^1J0K6{0V6}3e784:4=716@5;5o6j4(7f5w5,7E5:5=6~796H0M7y6N0/1d744v6M5^7K6g5|7H5Q1d547W3.6H0_7O4W7A6i5q5s6,6x5x7Z7z7J7;797V7u7m7,5}3u7v7(1d7N7%4b737@6.7#6:6=6M7,4Y7.6k5r6m804P7U1d0d5-7`7X7_7T6-7|817~6Y5.8n040q0.7O70864V7o6`6|8c824b5!2$0@0K0$8t3F8N8I7-5p8i4)4+89518p898f8%1d5H8H5:8l5u8B8D3^0m4R4L4w8{0m4z1L0@4B902=2.2c2e2:0V1|8}4z1R5O3I2$0*0O0H0V0X0^0O0v0e1d1D1F1H1J0;7i4N1#1W049r1l1H1u119t0;140;0y1l0/991}4.8`8Y7C8j8$8_4F3N1J0@0;0K2|9J9L9N1~0E0Q0#0J3L0^0h0;0s9u0-1u0k0Y9u0p0^0$2V0%0@2z9Z9^0k0B0;a32$9H9@5$0H0Y2$0k0@110V0p9}100;0$0Y0B8S2V0H0%0h1U3v1S0=3j9S0;2T8S0;3L1}0$0;2Z7m9L2j1ka20l1d090R0R0t0N0;0t0q097$7u0b8W2vaN0vaP0^aR04aT0R0iaX0ea!a$819}1s0;0j2;1~0-aq0$2WaD1l9!9$4#0~9$2Z0B1l0V2(0g6_2l1z2U9{aK1~0i9P9W000u001L9Qa89Z0ebr4S000Gbv9V4Saw1Yay040Wb7a.1E0p1}aX4Q9W010u0u0GbXbY01bw9WaKb3b5050V3I9+1?2b0#aRaK7s0V0M0@0,9}180/1k0E2Cb?0}0M0S0/0-2j180V1s4;c2b^4$b/c9cb2t0v2$0Hb}b 1J8_9S0O0(0o0h0%0y0E2t0-b@0M0{0%0B0M2T2V2X182c270#0*1_b~0EaG6{182t0%0$0Bcn0Vc00%cq5qcscucwcy2-0V2-9y1S0r0Q0;0,aGaG1s2pa41~8Z4(aD0#aFaH9~boa)21a+a-a/a;aWaYa_4-a(aMb4aO7sa.aSaUa?3Odf5(9Gbd0vbb9@c~bfbhbj4Ebl0%9{112ZbqbTbCbub$4Sby3ObB4LbDbF9QbIc:040wcN2Lahab11dC0pa2aJ0Tax1f7q3v1=04c=c@c_di2Wa,dldba=0_bA0I0;0za#4-be0$bg0@bi1JbId;1fd;d?c^b,d_dkaQdn0ie45(4#0#0/0ld1160/9a112o3n0/d$e2aD140B9|d2aJbQbgd51}11dJdRdLbG4Lec0/d:eV0u5r0K2W0^aXeNdQ04dSdM4LaDag369Ze(bAeKeG116_0}ah1JaX0%2paj0yeraJ9OeqesaX2Z1k0k0/eab80/9teU3v0md/9d9?0;370*0Jaadu7/d1d30QaId6ejd{ela:aUddaZeoa%d7c9djfAdmfCa=a@dr7u9YabfncNfqb11~9j0c9Ed6f62VaJbqe@9|1l6ke2dVbK0x1~fafcaa0E0Y9`e7bRfTfofWf$9SeyeIcSfxaL6Md9d|dnaVaXfFa`8Vdhg9fKdagc0kaX0*fQ81fS9Og0frfY0Vf!5rg2erf(fI01gafBaT0kfGa{eFf,eAgDgFfMgH0_0*gJ3Ff:9deY2lasd6aP0v0YaPff1I0%aX1uaD0^a}f20/aJ9GeGfUfpaafS6r9y303IgPdb0d090J35cN0:0kgS0?h90?0;e1090-0He70B0:0Rhagp0+hc0k0+0*hq098E8~4I9d0U0f9vd-05fk05d;fzglfChshf3r0P0A0P0e0P090B9^ai0Phn0M0(0q0PgIgg5u0medhHeVhJgbfChuhN0(hPhRhThV680%hY0*h!h$gTh)2-h,hIgjd`hKa;ho0q0+h?h^hShUhWh}hngSi0hYibgUh*h,fj0QbKbMaJbO1zbRhEhGi66-h2emide1h@hQhSeni31Li5h.i7ekgQ0R0eiGhOiJipi4eVeeiPiDgkh:a;0id icieiJ0P0i0P0C0P0D0Pe3iMh+i!1LhGh03.iEa:h4h6fo0:i+0ehc0ihehghihk0:iIh_i;i?i^0zhcjhiK091H0V2^0P0;jq0KjsiWhRjcjvjebg0:jki_jnifjBhhhjjEi?hU2peG0Q0:0D0?jHjgh`jQ7c0:iJ0?jB0e0Chw4yhz4y0|0~1004.