Problem
Start at the top-left corner of a grid with rows by columns cells. Move along cell edges only, one edge right or one edge down at a time, until reaching the bottom-right corner. Count distinct move sequences. The grid has no obstacles.
A grid with 2 rows and 3 columns of cells needs exactly 2 down moves and 3 right moves.
Implement lattice_paths(rows, columns).
Input
rows: The number of rows of cells, not vertices.
columns: The number of columns of cells, not vertices.
Output
Return the number of corner-to-corner routes.
Einschränkungen
0 ≤ rows, columns ≤ 30 and rows + columns ≤ 60. Zero in one dimension gives a straight route. A 0 × 0 grid has one empty route. Counts fit signed 64-bit.
Beispiele
Eingabe:
rows = 2
columns = 3
Erwartete Ausgabe:
expected = 10Eingabe:
long long rows = 2;
long long columns = 3;
Erwartete Ausgabe:
long long expected = 10;Eingabe:
long rows = 2;
long columns = 3;
Erwartete Ausgabe:
long expected = 10;Erläuterung
Every route contains five moves. Choosing which two are down gives ten distinct routes.
Eingabe:
rows = 0
columns = 4
Erwartete Ausgabe:
expected = 1Eingabe:
long long rows = 0;
long long columns = 4;
Erwartete Ausgabe:
long long expected = 1;Eingabe:
long rows = 0;
long columns = 4;
Erwartete Ausgabe:
long expected = 1;Erläuterung
There is only the straight route of four right moves.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Each route is just an ordering of the required down and right moves.
Hinweis 2
Count how many ways to choose the positions of one move type among all moves, rather than exploring paths one by one.
Hinweis 3
Watch the degenerate grids: if one dimension is zero, there is exactly one straight route, and a 0×0 grid still has one empty route.
Erwartete Komplexität
O(min(rows, columns)) time, O(1) extra space
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.