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

.128013u;5UD}0_[-q,94:ùdfm?çgrE8kb(i]R{!nl.x12CPa Soè3O)yàv×=wpsh6c+tLeê7é/NI050r0:0.0Q0D0J0)0R0,0J0Q0)0)0$010.0D0(010406050)0b0t0t0Q0x0Y040S0T0J0b1a0T0I0R020Q0t0(0c0R0F0:1k0x0l0b0:0)050@1h1j1l1n1f0(04051S1L1V0@1S1f0r0D0!121416180*0D0w0*0J1-0*0.1d050}0B0J0:1(1517011,1.1:1.0.1_1{1@0.0x1T0.0*121q0)0(0Q0I180N011}1*010s0 0:0I1y0:1@2g2i2n1 2q1{2t0t2v040a0R0P0x0T0(0T0)0D1t1v0{2e0x0x0:0,2Q1L2x0I1T0@2c2$292b2a1^0r2z181:0I2s2N1@1#1%131~2:0D2=0I0T2_1@0(2V1T2!2$371g2h1v2{2o300x1k0J1d0R0M2Z3b1e3a2y3d1 3f3h3j0N3m2i3o2!2/013t0Q3i040R0V3x2#1f3A3r183D3F0R0o3J3z3b3B3P3j0d3T3L3V3N3C0T3g3E3j0+3!3p3c1)3s3)3u3G0=3.3M3;3O3?3+3G0z3`3$3|3(3*3Q0n423q443X040M0h493:2|453@0M3l1M3n1W351L2_2)0r2b2.3%0,312F0`1$1T340:364o4n3y054y0{4G4a4i0I1d0I0B0i0,0*1E2~0)0i2E0t3T0R3/3B0T1d0$4%4)3%4S1d1#2X3T4/441c040C0X3!063#4O2o0A4=0:0s4^3{4i0%3j58434P0s4R4T4V4X0I1K4I2#4_4i4{0C5d523s4R5t4h2o4{0m4.593e1d4$5n4N5y1 4{0X0p3!0R5P4(5D1 54040D575H5R5e5z1d5s5H5p5E040I5x3B5A5C5!5v045G395S185L5:5u180T5b5+0T0.5|5J5~602~643W5h4U4W0t4Y4!1E5-3%4{5N5H065Q6o5Z5}015U5W694:5w5Y5)1 4+040$4-6y5_016e1d4f6F5;661d3)6v4b5F6Q4i6B6D6T2o6I046K5^6M016k5O6p6+6z3O1d2V1h0J0}636L6r6V6X1 6Z4m376n6+6q656s1d0:100:6i4`1d6l6 716p6-3C6/1J0b6=0Q6@37724*4,6{6.5+5i6d4Y795q5$7y5*5,6^736B0k7s6H0D1d6~4o6G5/7E6a5?7B5K1d4~7Q3%6B0-7I4Q7u6c5k5m6$6r5r7T7t7D7+737P7o7g7$5@3n7p7Y1d7H7X446}7.6(7V6*6,6G7$4S7(6e5l6g7`4J7O1d0j5%7;7R7:7N6%7?7{7^6S5(8h040X0E7I6`804P7i6;6?867|445U2V0.0b0x8n3y8H8C7%5j8c4Z4#834{8j83898X1d5B8B5*8f5o8v8x3.0@4L4F4p8=0@4s1L0.4u8`2,2%0Q1`8@4s1R5I3B2V0t0i0s0Q0A0:0i0*0V1d1D1F1H1J0R7c4H1Z1U049i1l1H1u119k0R140R0!1l0D901{4(8;8S7w8d8W8:4z3G1J0.0R0b2=9A9C9E1|0w0J0T0B3E0:0K0R0/9l0r1u0I0?9l0(0:0x2O0)0.2s9Q9,0I0,0R9`2V9y9+5W0s0?2V0I0.110Q0(9;100R0x0?0,8M2O0s0)0K1W3o1S0e3c9J0R2M8M0R3E1{0x0R2S7g9C2c1k9_0L1d090C0C0h0m0R0h0X097W7o0Z8Q2oaE0*aG0:aI04aK0C0oaO0VaRaT7{9;1s0R0;291|0rah0x2Pau1l9R9T4V0~9T2S0,1l0Q2X0U6:2e1z2N9/aB1|0o9G9N000y001L9H9 9Q0Vbi4M000^bm9M4Man1Yap040Pa~a#1E0(1{aO4K9N010y0y0^bObP01bn9NaBa`a|050Q3B9Y1;0.0B0TaI0R0*2V0s180D1k0w1J8:9J0i0M0z0K0)0!0w2m0r7m0Q0k0.0Y9;b/b;2vaBc20k0%0D0r2c180Q1s4+cb0}0k4Wb$cickc0cc0{0)0,0k2M2O2Q18b(250T0t1@b:0wax6=182m0)0x0,c80Qb=0)b@5kb_b{b}b 0R0@2$0Q2$9p1S0_0J0R0Yaxax1s2i9{1|8T4Yau0Taway9=bfaW1 aYa!a$a(aNaPa-4%aVaDa{aF7ma#aJaLa*3Hd95Y9xb40*b29+c^b6b8ba4ybc0)9/112SbhbKbtblbT4Mbp3Hbs4Fbubw9Hbzc*040OcF2Ea8a211dw0(9_aA0uao1f7k3o1:04c,c.c:dc2PaZdfd5a)0-br0$0R0=aS4%b50xb70.b91Jbzd+1fd+d-c/bZd:deaHdh0od~5Y4V0T0D0Lc{160D91112h3g0DdWd|au140,9:c|aAbHb7c 1{11dDdLdFbx4Fe60Dd*eP0y5l0b2P0:aOeHdK04dMdG4Faua72 9QeYbreEeA116:0}a81JaO0)2iaa0!elaA9FekemaO2S1k0I0De4a 0D9keO3o0@d)949*0R300t0Ba1do7)c{c}0Jazd0edd=efa%aLd7aQeiaUd1ciddfudgfwa)a+dl7o9Pa2fhcFfka^1|9a0v9vd0f02OaAbhe.9:1l6ed|dPbB0f1|f4f6a10w0?9.e1bIfNfifQfW9JeseCcKfraC6Gd3d?dhaMaOfza.8Pdbg3fEd4g60IaO0tfK7{fM9Ff`flfS0QfU5lf|elfYfC01g4fvaK0IfAa/ezf$eugxgzfGgB0-0tgD3yf*94eS2eajd0aG0*0?aGf91I0)aO1uau0:a;e|0DaA9xeAfOfja1fM6l9p2_3BgJd50j090B2~cF0G0IgM0gh30g0Rd{090r0se10,0G0Ch4gj0Hh60I0H0thk098y8^4C940W0q9md%05fe05d+ftgffwhmh93k0#0N0#0V0#090,9,a90#hh0k0M0X0#gCga5o0@e7hBePhDg5fwhohH0MhJhLhNhP620)hS0thUhWgNhZ2$h$hCgdd;hEa(hi0X0Hh-h/hMhOhQh@hhgMh`hSi5gOh!h$fd0JbBbDaAbF1zbIhyhAi06%g|egi7d{h.hKhMehh}1Lh h(i1eegK0C0ViAhIiDijh~ePe8iJixgeh*a(0od_i6i8iD0#0o0#0d0#0+0#d}iGh#iU1LhAg`3%iya%g~h0fi0Gi#0Vh60oh8hahche0GiCh:i+i-i/0=h6jbiE091H0Q2.0#0Rjk0bjmiQhLj6jpj8b70Gjei:jhi9jvhbhdjyi-hO2ieA0J0G0+0gjBjah;jK760GiD0gjv0V0dhq4rht4r0|0~1004.

Évaluations restantes : 10/10

.128013u;5UD}0_[-q,94:ùdfm?çgrE8kb(i]R{!nl.x12CPa Soè3O)yàv×=wpsh6c+tLeê7é/NI050r0:0.0Q0D0J0)0R0,0J0Q0)0)0$010.0D0(010406050)0b0t0t0Q0x0Y040S0T0J0b1a0T0I0R020Q0t0(0c0R0F0:1k0x0l0b0:0)050@1h1j1l1n1f0(04051S1L1V0@1S1f0r0D0!121416180*0D0w0*0J1-0*0.1d050}0B0J0:1(1517011,1.1:1.0.1_1{1@0.0x1T0.0*121q0)0(0Q0I180N011}1*010s0 0:0I1y0:1@2g2i2n1 2q1{2t0t2v040a0R0P0x0T0(0T0)0D1t1v0{2e0x0x0:0,2Q1L2x0I1T0@2c2$292b2a1^0r2z181:0I2s2N1@1#1%131~2:0D2=0I0T2_1@0(2V1T2!2$371g2h1v2{2o300x1k0J1d0R0M2Z3b1e3a2y3d1 3f3h3j0N3m2i3o2!2/013t0Q3i040R0V3x2#1f3A3r183D3F0R0o3J3z3b3B3P3j0d3T3L3V3N3C0T3g3E3j0+3!3p3c1)3s3)3u3G0=3.3M3;3O3?3+3G0z3`3$3|3(3*3Q0n423q443X040M0h493:2|453@0M3l1M3n1W351L2_2)0r2b2.3%0,312F0`1$1T340:364o4n3y054y0{4G4a4i0I1d0I0B0i0,0*1E2~0)0i2E0t3T0R3/3B0T1d0$4%4)3%4S1d1#2X3T4/441c040C0X3!063#4O2o0A4=0:0s4^3{4i0%3j58434P0s4R4T4V4X0I1K4I2#4_4i4{0C5d523s4R5t4h2o4{0m4.593e1d4$5n4N5y1 4{0X0p3!0R5P4(5D1 54040D575H5R5e5z1d5s5H5p5E040I5x3B5A5C5!5v045G395S185L5:5u180T5b5+0T0.5|5J5~602~643W5h4U4W0t4Y4!1E5-3%4{5N5H065Q6o5Z5}015U5W694:5w5Y5)1 4+040$4-6y5_016e1d4f6F5;661d3)6v4b5F6Q4i6B6D6T2o6I046K5^6M016k5O6p6+6z3O1d2V1h0J0}636L6r6V6X1 6Z4m376n6+6q656s1d0:100:6i4`1d6l6 716p6-3C6/1J0b6=0Q6@37724*4,6{6.5+5i6d4Y795q5$7y5*5,6^736B0k7s6H0D1d6~4o6G5/7E6a5?7B5K1d4~7Q3%6B0-7I4Q7u6c5k5m6$6r5r7T7t7D7+737P7o7g7$5@3n7p7Y1d7H7X446}7.6(7V6*6,6G7$4S7(6e5l6g7`4J7O1d0j5%7;7R7:7N6%7?7{7^6S5(8h040X0E7I6`804P7i6;6?867|445U2V0.0b0x8n3y8H8C7%5j8c4Z4#834{8j83898X1d5B8B5*8f5o8v8x3.0@4L4F4p8=0@4s1L0.4u8`2,2%0Q1`8@4s1R5I3B2V0t0i0s0Q0A0:0i0*0V1d1D1F1H1J0R7c4H1Z1U049i1l1H1u119k0R140R0!1l0D901{4(8;8S7w8d8W8:4z3G1J0.0R0b2=9A9C9E1|0w0J0T0B3E0:0K0R0/9l0r1u0I0?9l0(0:0x2O0)0.2s9Q9,0I0,0R9`2V9y9+5W0s0?2V0I0.110Q0(9;100R0x0?0,8M2O0s0)0K1W3o1S0e3c9J0R2M8M0R3E1{0x0R2S7g9C2c1k9_0L1d090C0C0h0m0R0h0X097W7o0Z8Q2oaE0*aG0:aI04aK0C0oaO0VaRaT7{9;1s0R0;291|0rah0x2Pau1l9R9T4V0~9T2S0,1l0Q2X0U6:2e1z2N9/aB1|0o9G9N000y001L9H9 9Q0Vbi4M000^bm9M4Man1Yap040Pa~a#1E0(1{aO4K9N010y0y0^bObP01bn9NaBa`a|050Q3B9Y1;0.0B0TaI0R0*2V0s180D1k0w1J8:9J0i0M0z0K0)0!0w2m0r7m0Q0k0.0Y9;b/b;2vaBc20k0%0D0r2c180Q1s4+cb0}0k4Wb$cickc0cc0{0)0,0k2M2O2Q18b(250T0t1@b:0wax6=182m0)0x0,c80Qb=0)b@5kb_b{b}b 0R0@2$0Q2$9p1S0_0J0R0Yaxax1s2i9{1|8T4Yau0Taway9=bfaW1 aYa!a$a(aNaPa-4%aVaDa{aF7ma#aJaLa*3Hd95Y9xb40*b29+c^b6b8ba4ybc0)9/112SbhbKbtblbT4Mbp3Hbs4Fbubw9Hbzc*040OcF2Ea8a211dw0(9_aA0uao1f7k3o1:04c,c.c:dc2PaZdfd5a)0-br0$0R0=aS4%b50xb70.b91Jbzd+1fd+d-c/bZd:deaHdh0od~5Y4V0T0D0Lc{160D91112h3g0DdWd|au140,9:c|aAbHb7c 1{11dDdLdFbx4Fe60Dd*eP0y5l0b2P0:aOeHdK04dMdG4Faua72 9QeYbreEeA116:0}a81JaO0)2iaa0!elaA9FekemaO2S1k0I0De4a 0D9keO3o0@d)949*0R300t0Ba1do7)c{c}0Jazd0edd=efa%aLd7aQeiaUd1ciddfudgfwa)a+dl7o9Pa2fhcFfka^1|9a0v9vd0f02OaAbhe.9:1l6ed|dPbB0f1|f4f6a10w0?9.e1bIfNfifQfW9JeseCcKfraC6Gd3d?dhaMaOfza.8Pdbg3fEd4g60IaO0tfK7{fM9Ff`flfS0QfU5lf|elfYfC01g4fvaK0IfAa/ezf$eugxgzfGgB0-0tgD3yf*94eS2eajd0aG0*0?aGf91I0)aO1uau0:a;e|0DaA9xeAfOfja1fM6l9p2_3BgJd50j090B2~cF0G0IgM0gh30g0Rd{090r0se10,0G0Ch4gj0Hh60I0H0thk098y8^4C940W0q9md%05fe05d+ftgffwhmh93k0#0N0#0V0#090,9,a90#hh0k0M0X0#gCga5o0@e7hBePhDg5fwhohH0MhJhLhNhP620)hS0thUhWgNhZ2$h$hCgdd;hEa(hi0X0Hh-h/hMhOhQh@hhgMh`hSi5gOh!h$fd0JbBbDaAbF1zbIhyhAi06%g|egi7d{h.hKhMehh}1Lh h(i1eegK0C0ViAhIiDijh~ePe8iJixgeh*a(0od_i6i8iD0#0o0#0d0#0+0#d}iGh#iU1LhAg`3%iya%g~h0fi0Gi#0Vh60oh8hahche0GiCh:i+i-i/0=h6jbiE091H0Q2.0#0Rjk0bjmiQhLj6jpj8b70Gjei:jhi9jvhbhdjyi-hO2ieA0J0G0+0gjBjah;jK760GiD0gjv0V0dhq4rht4r0|0~1004.