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),
    • ces deux catégories sont distinctes et se comptent bien par récursivité.
  • 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 :

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5
.65038.9875.128013lS]te-Ud5!f18umaèg,_/çR={in 6)yàqPhcDNL\[(bùEsx.p;r4C'90"ov+w73?êOk:é }2I×030e0b0a0m0w070Q0;0G070m0Q0Q0u0#0a0w0T0#020y030Q0k0l0l0m0V0B02080$070k190$0x0;000m0l0T0U0;0t0b1j0V0D0k0b0Q030r1g1i1k1m1e0T02031R1K1U0r1R1e0e0w0%111315170F0w0o0F071+0F0a1c030|0N070b1%14160#1*1,1.1,0a1@1_1=0a0V1S0a0F111p0Q0T0m0x170?0#1{1(0#0h0~0b0x1x0b1=2e2g2l1}2o1_2r0l2t02060;0E0V0$0T0$0Q0w1s1u0`2c0V0V0b0G2O1K2v0x1S0r2a2!2729281?0e2x171.0x2q2L1=1!1$121|2-0w2/0x0$2?1=0T2T1S2Y2!341f2f1u2^2m2}0V1j071c0;0i2X381d372w3a1}3c3e3g0?3j2g3l2Y2,0#3q0m3f020;0*3u2Z1e3x3o173A3C0;0W3G3w383y3M3g0f3Q3I3S3K3z0$3d3B3g0z3X3m391'3p3$3r3D0)3*3J3-3L3/3'3D0j3?3Z3^3#3%3N0Z3~3n403U020i0!453,2_413:0i3i1L3k1V321K2?2%0e292+3!0G2~2D0_1#1S310b334k4j3v034u0`4C464e0x1c0x0N0q0G0F1D2{0Q0q2C0l3Q0;3+3y0$1c0u4Z4#3!4O1c1!2V3Q4*401b020M0A3X0y3Y4K2m0.4-0b0h4)3@4L0h4N4P4R4T0x1J4E2Z4;4e4?0M4:543b4N5j3 5g1c0p535o5l024Y5d4J4d2m4?0A0/3X0;5F4!5k1}4 020w525x5H5t1}5h5n4}3p5m5x5f5A5q5s5U3L1c5w365I175B5#5z1}0$0(4N0$0a5-4$5;5L0x5^4+574Q4S0l4U4W1D5T5.5+1c5D5x0y5G6d5P5$0#5K5M5}4=1c5i5X5*3z5W346f670#4%020u4(5O5Y1}621c4b6o5Q68024_6A6p5:1c3$6k5p4@663T5'6Q2m6w6y6W6C0w6E6T3!5B6a346c6e6-6B5%022T1g070|5@6L6H6v4'6!176D495E6-6t3y5K0b0 0b6'6l026*3k6,735G6/6q6;1I0k6@0m6_6s7i6Y6~7j4O605a5c5)6{5S6G6g4M025|6`6g6w0c7t704i7z6g4?5r7H6u7E5(4k6p5,7S4$1c0'7t7E7v59625b7a6R6n7O7T6r7W7A5!7Z5~5v7t7J7L6$717C6u7Y6+7g7i7'5861634X7,5Z020L7.7=7D7;4F7X7@7q6p7U8b5R1c0A097{6}7^471c6=7m6^725F7i5K2T0a0k0V7G8m6{867w7*4V8a803y4?8e8p6:8K8g818l3k747_7V8j7?6J8t6b1K4H4B4l8:0r4o1K0a4q8^2)2#0m1^8=4o1Q5y3y2T0l0q0h0m0.0b0q0F0*1c1C1E1G1I0;7d4F1X3l1R0d2/0;0m0e0m0T6^0w1t0;1!2T2V1`0`102{4.7o9y5b9A1`070Y0:2}0x0G0:0S1V3l0F0i0;0w0e174u1y1_2C0x0a0Q1c0X0$9(0:9*9,030m3y4S9t0b0V2.4 0;0F2T0h17019'0T9)2q9,2k190a1_170E9}1j2|0a0;9 1c05041K0m2!9Y9o029q11881u2K8I9s071_0V9M8%401k2N0F1j0a0b0R1c0K0M0M0!0p0;0!0A0K6K6s0CaI4eaK2aaNaPaRaT0WaW0*aZa#8$0T0b1r0;0,279E0:0G0V2N0;2faG0k9r4R0}9r2Q0G1k0m2V0n6=2c1y2L0:9E1`0W4!8/020Y0P0Y8.4v3D0{3Ebpbw0Y0Ibu0rbq9V9n920E1k0;aP1Da80baW4Gbw0#0P0P0IbWbX0#bv4I9Aa b1al030w0l0oaD0a172k0Q0V0G17b+0m0o1IbFaz0q0i0j0S0Q0%0o2k0r2!1Y1T020@070;0B9s9s1r2galbbaz10aBaG3BaFaH7ia)aM7oa,02aSaUaWaYa!4Za%ctb(cvaOaQcya.a:a=4Z9iaHb82{9jbbbdbfbha7bkcUbnbA4IbsbEbqbMal0*c%4BbCc)bwbHc91R9/1iaaam9ja7aOaG0+9W1e7m3l1.cbcdcf9_cGaLa+cKaS0W0'c-0u0;0)cD5Obc0Vbe0abg1IbHd61ed6cccecgdba*cwde0M0Wdm6s4R0$0w0Rb32L2M8 cn1k62c|100)b3130G9jcodXbe9}dUc.brbtb#4Bdu0wd5d/0P5b0k2NbQd(bSc'bDd,3D4A0xakd(c-a8d%106=0|9+1IaW0Q2g100m0%dKaG1_aydK0RaW2Qaj0wds0;b60w9id.3l0rd4920J1`2}0l0N2TcRcmdNaCcqd'2QdBcIcxczaVaXcO5OcF6pcudda-dFcNdH8$1IalekeEeGbm0;980s1t10cldK2MaGboe5dZdR3d0wdkc?av0H1`eqes0o9Q0:dp1_aWe+9:e-eI7xeKcpaEeN1`ePe!cLcAeUe'3v0;eX6{eZdDe#0xaW0leV6se)c|0;e,eH2Qe:e=eIe^0waGfofzcL0xft2Zd$e}b3dSf0fScJa-0x0'0lfW02f292d=2c8Ie?f57o0F9=9J9i0QaW9za^a`ehfQ0;cQdZfIffeHfG6ac92?3yfyf'cy0L0K0N2{9:0v0x0=gnf*0=0;dj0K0e0hdp0G0v0Mf)fD0ggp0x0g0lgE0K8,91ca0-0O9kd203eA03d6f%eRgB0ggt3h0^0?0^0*0^0K0G0e5?0Q0^gB0c0i0A0^fVa?9mdvgUd/gWdEgIg!0ig$g'g)g+g-g/0lg;g?f+g_5e0rg{gVeYcHfpczgC0AgZdjh2g%g(g*g,9,g/gChahwf*fE4Dg{ez07avbKaGbN9(bQgRgThhfxhjfTdfhog#hr0^dGhd2!hgg}hidchR0M0*hThqg'f,1Kh!933!gfgXdFdhhnh1h3g(0W0^0f0^0z0^dlhYh.d/1ehE3lgdh;hQgg0KgigkeE0v0Wgpdg0*gsgugwgy0vh+h|h~i0i2gpishW0K1G9t0;0^0;iA0kiCisiniFipbe0vh i10)ixh{iKgvgxiNh g*2gdZ070v0z0=iwirh5i!770vhr0=iK0*0fgK4n4yi70`0|0~0Q02.