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

.1280133ytbIqO)N4ê_7u:k}8×s(ar5.lRàLvU21m+ép;=cxS,i6fdgç[!he P]èow/Cn0ED-ù?9{050V0#0d0w0S0A0u0$0O0A0w0u0u0N010d0S0L010406050u0o0I0I0w0x0c040Q0*0A0o1a0*0.0$020w0I0L0M0$0B0#1k0x0g0o0#0u050,1h1j1l1n1f0L041L1S051V0,1V1X1S1f0V0S0E121416180!0S0W0!0A1/0!0d1d050}0e0A0#1*1517011.1:1=1:0d1{1}1_0d0e0*0V1n1`0x1T0d0!121q0u0L0w0.180G011 1,010U0 0#0.1y0#1_2n2p2u212x1}2A0I2C040a0$0%0x0*0L0*0u0S1t1v0{2l0x0x0#0O2X1L2E0.1T0,2j2-0d2h2g2i0V2G181=0.2z2U1_1%1)13202`0S2|0.2d1(1_0L2$1T2+2-3e1g2o1v322v370x1k0A1d0$0H2*3i1e3h2F3k213m3o3q0G3t2p3v2+2_013A0w3p040$0b3E2,1f3H3y183K3M0$0k3Q3G3i3I3W3q0y3!3S3$3U3J0*3n3L3q0T3+3w3j1+3z3:3B3N0n3^3T3{3V3}3=3N0s413-433/3;3X0^493x4b3(040H0/4g3`334c3~0H3s1M3u1U3c1L302:0V2@3I0O2d2M0`1(1T3b0#3d4v4u3F054E0{4M4h4p0.1d0.0e0m0O0!1E350u0m2L0I3!0$3_3I0*1d0N4-4/3.4Y1d1%2(3!4^4b1c040v0i3+063,4U2v0q4{0#0U4~424p0+3q5e4a4V0U4X4Z4#4%0.1K4O2,4 4p510v5j583z4X5z4o2v510R4@5f3l1d4,5t4T5E21510i0p3+0$5V4.5J215a040S5d5N5X5k5F1d5y5N5v5K040.5D3I5G5I5*5B045M3g5Y185R5_5A180*5h5;0*0d625P6466356a3%5n4!4$0I4(4*1E5?3.515T5N065W6u5)63015!5$6f4_5C5(5/214;040N4?6E5 016k1d4m6L5`6c1d3:6B4i5L6W4p6H6J6Z2v6O046Q5~6S016q5U6v6;6F3V1d2$1h0A0}696R6x6#6%216)4t3e6t6;6w6b6y1d0#100#6o501d6r75776v6?3J6^1J0o6{0w6}3e784:4=716@5;5o6j4(7f5w5,7E5:5=6~796H0=7y6N0S1d744v6M5^7K6g5|7H5Q1d547W3.6H0J7O4W7A6i5q5s6,6x5x7Z7z7J7;797V7u7m7,5}3u7v7(1d7N7%4b737@6.7#6:6=6M7,4Y7.6k5r6m804P7U1d0Y5-7`7X7_7T6-7|817~6Y5.8n040i0(7O70864V7o6`6|8c824b5!2$0d0o0x8t3F8N8I7-5p8i4)4+89518p898f8%1d5H8H5:8l5u8B8D3^0,4R4L4w8{0,4z1L0d4B902=2.2c2e2:0w1|8}4z1R5O3I2$0I0m0U0w0q0#0m0!0b1d1D1F1H1J0$7i4N1#1W049r1l1H1u119t0$140$0E1l0S991}4.8`8Y7C8j8$8_4F3N1J0d0$0o2|9J9L9N1~0W0A0*0e3L0#0z0$0D9u0V1u0.0K9u0L0#0x2V0u0d2z9Z9^0.0O0$a32$9H9@5$0U0K2$0.0d110w0L9}100$0x0K0O8S2V0U0u0z1U3v1S0F3j9S0$2T8S0$3L1}0x0$2Z7m9L2j1ka20P1d090v0v0/0R0$0/0i097$7u0C8W2vaN0!aP0#aR04aT0v0kaX0ba!a$819}1s0$0l2;1~0Vaq0x2WaD1l9!9$4#0~9$2Z0O1l0w2(0)6_2l1z2U9{aK1~0k9P9W000:001L9Qa89Z0bbr4S000jbv9V4Saw1Yay040%b7a.1E0L1}aX4Q9W010:0:0jbXbY01bw9WaKb3b5050w3I9+1?2b0*aRaK7s0w0=0d0c9}180S1k0W2Cb?0}0=0+0S0V2j180w1s4;c2b^4$b/c9cb2t0!2$0Ub}b 1J8_9S0m0H0s0z0u0E0W2t0Vb@0=0{0u0O0=2T2V2X182c270*0I1_b~0WaG6{182t0u0x0Ocn0wc00ucq5qcscucwcy2-0w2-9y1S0f0A0$0caGaG1s2pa41~8Z4(aD0*aFaH9~boa)21a+a-a/a;aWaYa_4-a(aMb4aO7sa.aSaUa?3Odf5(9Gbd0!bb9@c~bfbhbj4Ebl0u9{112ZbqbTbCbub$4Sby3ObB4LbDbF9QbIc:040-cN2Lahab11dC0La2aJ0@ax1f7q3v1=04c=c@c_di2Wa,dldba=0JbA0N0$0na#4-be0xbg0dbi1JbId;1fd;d?c^b,d_dkaQdn0ke45(4#0*0S0Pd1160S9a112o3n0Sd$e2aD140O9|d2aJbQbgd51}11dJdRdLbG4Lec0Sd:eV0:5r0o2W0#aXeNdQ04dSdM4LaDag369Ze(bAeKeG116_0}ah1JaX0u2paj0EeraJ9OeqesaX2Z1k0.0Seab80S9teU3v0,d/9d9?0$370I0eaadu7/d1d30AaId6ejd{ela:aUddaZeoa%d7c9djfAdmfCa=a@dr7u9YabfncNfqb11~9j0X9Ed6f62VaJbqe@9|1l6ke2dVbK0;1~fafcaa0W0K9`e7bRfTfofWf$9SeyeIcSfxaL6Md9d|dnaVaXfFa`8Vdhg9fKdagc0.aX0IfQ81fS9Og0frfY0wf!5rg2erf(fI01gafBaT0.fGa{eFf,eAgDgFfMgH0J0IgJ3Ff:9deY2lasd6aP0!0KaPff1I0uaX1uaD0#a}f20SaJ9GeGfUfpaafS6r9y303IgPdb0Y090e35cN0_0.gS0rh90r0$e1090V0Ue70O0_0vhagp0Zhc0.0Z0Ihq098E8~4I9d0h0?9vd-05fk05d;fzglfChshf3r0t0G0t0b0t090O9^ai0thn0=0H0i0tgIgg5u0,edhHeVhJgbfChuhN0HhPhRhThV680uhY0Ih!h$gTh)2-h,hIgjd`hKa;ho0i0Zh?h^hShUhWh}hngSi0hYibgUh*h,fj0AbKbMaJbO1zbRhEhGi66-h2emide1h@hQhSeni31Li5h.i7ekgQ0v0biGhOiJipi4eVeeiPiDgkh:a;0kd icieiJ0t0k0t0y0t0T0te3iMh+i!1LhGh03.iEa:h4h6fo0_i+0bhc0khehghihk0_iIh_i;i?i^0nhcjhiK091H0w2^0t0$jq0ojsiWhRjcjvjebg0_jki_jnifjBhhhjjEi?hU2peG0A0_0T0rjHjgh`jQ7c0_iJ0rjB0b0yhw4yhz4y0|0~1004.

Évaluations restantes : 10/10

.1280133ytbIqO)N4ê_7u:k}8×s(ar5.lRàLvU21m+ép;=cxS,i6fdgç[!he P]èow/Cn0ED-ù?9{050V0#0d0w0S0A0u0$0O0A0w0u0u0N010d0S0L010406050u0o0I0I0w0x0c040Q0*0A0o1a0*0.0$020w0I0L0M0$0B0#1k0x0g0o0#0u050,1h1j1l1n1f0L041L1S051V0,1V1X1S1f0V0S0E121416180!0S0W0!0A1/0!0d1d050}0e0A0#1*1517011.1:1=1:0d1{1}1_0d0e0*0V1n1`0x1T0d0!121q0u0L0w0.180G011 1,010U0 0#0.1y0#1_2n2p2u212x1}2A0I2C040a0$0%0x0*0L0*0u0S1t1v0{2l0x0x0#0O2X1L2E0.1T0,2j2-0d2h2g2i0V2G181=0.2z2U1_1%1)13202`0S2|0.2d1(1_0L2$1T2+2-3e1g2o1v322v370x1k0A1d0$0H2*3i1e3h2F3k213m3o3q0G3t2p3v2+2_013A0w3p040$0b3E2,1f3H3y183K3M0$0k3Q3G3i3I3W3q0y3!3S3$3U3J0*3n3L3q0T3+3w3j1+3z3:3B3N0n3^3T3{3V3}3=3N0s413-433/3;3X0^493x4b3(040H0/4g3`334c3~0H3s1M3u1U3c1L302:0V2@3I0O2d2M0`1(1T3b0#3d4v4u3F054E0{4M4h4p0.1d0.0e0m0O0!1E350u0m2L0I3!0$3_3I0*1d0N4-4/3.4Y1d1%2(3!4^4b1c040v0i3+063,4U2v0q4{0#0U4~424p0+3q5e4a4V0U4X4Z4#4%0.1K4O2,4 4p510v5j583z4X5z4o2v510R4@5f3l1d4,5t4T5E21510i0p3+0$5V4.5J215a040S5d5N5X5k5F1d5y5N5v5K040.5D3I5G5I5*5B045M3g5Y185R5_5A180*5h5;0*0d625P6466356a3%5n4!4$0I4(4*1E5?3.515T5N065W6u5)63015!5$6f4_5C5(5/214;040N4?6E5 016k1d4m6L5`6c1d3:6B4i5L6W4p6H6J6Z2v6O046Q5~6S016q5U6v6;6F3V1d2$1h0A0}696R6x6#6%216)4t3e6t6;6w6b6y1d0#100#6o501d6r75776v6?3J6^1J0o6{0w6}3e784:4=716@5;5o6j4(7f5w5,7E5:5=6~796H0=7y6N0S1d744v6M5^7K6g5|7H5Q1d547W3.6H0J7O4W7A6i5q5s6,6x5x7Z7z7J7;797V7u7m7,5}3u7v7(1d7N7%4b737@6.7#6:6=6M7,4Y7.6k5r6m804P7U1d0Y5-7`7X7_7T6-7|817~6Y5.8n040i0(7O70864V7o6`6|8c824b5!2$0d0o0x8t3F8N8I7-5p8i4)4+89518p898f8%1d5H8H5:8l5u8B8D3^0,4R4L4w8{0,4z1L0d4B902=2.2c2e2:0w1|8}4z1R5O3I2$0I0m0U0w0q0#0m0!0b1d1D1F1H1J0$7i4N1#1W049r1l1H1u119t0$140$0E1l0S991}4.8`8Y7C8j8$8_4F3N1J0d0$0o2|9J9L9N1~0W0A0*0e3L0#0z0$0D9u0V1u0.0K9u0L0#0x2V0u0d2z9Z9^0.0O0$a32$9H9@5$0U0K2$0.0d110w0L9}100$0x0K0O8S2V0U0u0z1U3v1S0F3j9S0$2T8S0$3L1}0x0$2Z7m9L2j1ka20P1d090v0v0/0R0$0/0i097$7u0C8W2vaN0!aP0#aR04aT0v0kaX0ba!a$819}1s0$0l2;1~0Vaq0x2WaD1l9!9$4#0~9$2Z0O1l0w2(0)6_2l1z2U9{aK1~0k9P9W000:001L9Qa89Z0bbr4S000jbv9V4Saw1Yay040%b7a.1E0L1}aX4Q9W010:0:0jbXbY01bw9WaKb3b5050w3I9+1?2b0*aRaK7s0w0=0d0c9}180S1k0W2Cb?0}0=0+0S0V2j180w1s4;c2b^4$b/c9cb2t0!2$0Ub}b 1J8_9S0m0H0s0z0u0E0W2t0Vb@0=0{0u0O0=2T2V2X182c270*0I1_b~0WaG6{182t0u0x0Ocn0wc00ucq5qcscucwcy2-0w2-9y1S0f0A0$0caGaG1s2pa41~8Z4(aD0*aFaH9~boa)21a+a-a/a;aWaYa_4-a(aMb4aO7sa.aSaUa?3Odf5(9Gbd0!bb9@c~bfbhbj4Ebl0u9{112ZbqbTbCbub$4Sby3ObB4LbDbF9QbIc:040-cN2Lahab11dC0La2aJ0@ax1f7q3v1=04c=c@c_di2Wa,dldba=0JbA0N0$0na#4-be0xbg0dbi1JbId;1fd;d?c^b,d_dkaQdn0ke45(4#0*0S0Pd1160S9a112o3n0Sd$e2aD140O9|d2aJbQbgd51}11dJdRdLbG4Lec0Sd:eV0:5r0o2W0#aXeNdQ04dSdM4LaDag369Ze(bAeKeG116_0}ah1JaX0u2paj0EeraJ9OeqesaX2Z1k0.0Seab80S9teU3v0,d/9d9?0$370I0eaadu7/d1d30AaId6ejd{ela:aUddaZeoa%d7c9djfAdmfCa=a@dr7u9YabfncNfqb11~9j0X9Ed6f62VaJbqe@9|1l6ke2dVbK0;1~fafcaa0W0K9`e7bRfTfofWf$9SeyeIcSfxaL6Md9d|dnaVaXfFa`8Vdhg9fKdagc0.aX0IfQ81fS9Og0frfY0wf!5rg2erf(fI01gafBaT0.fGa{eFf,eAgDgFfMgH0J0IgJ3Ff:9deY2lasd6aP0!0KaPff1I0uaX1uaD0#a}f20SaJ9GeGfUfpaafS6r9y303IgPdb0Y090e35cN0_0.gS0rh90r0$e1090V0Ue70O0_0vhagp0Zhc0.0Z0Ihq098E8~4I9d0h0?9vd-05fk05d;fzglfChshf3r0t0G0t0b0t090O9^ai0thn0=0H0i0tgIgg5u0,edhHeVhJgbfChuhN0HhPhRhThV680uhY0Ih!h$gTh)2-h,hIgjd`hKa;ho0i0Zh?h^hShUhWh}hngSi0hYibgUh*h,fj0AbKbMaJbO1zbRhEhGi66-h2emide1h@hQhSeni31Li5h.i7ekgQ0v0biGhOiJipi4eVeeiPiDgkh:a;0kd icieiJ0t0k0t0y0t0T0te3iMh+i!1LhGh03.iEa:h4h6fo0_i+0bhc0khehghihk0_iIh_i;i?i^0nhcjhiK091H0w2^0t0$jq0ojsiWhRjcjvjebg0_jki_jnifjBhhhjjEi?hU2peG0A0_0T0rjHjgh`jQ7c0_iJ0rjB0b0yhw4yhz4y0|0~1004.