समस्या
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.
सीमाएँ
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.
उदाहरण
इनपुट:
rows = 2
columns = 3
अपेक्षित आउटपुट:
expected = 10इनपुट:
long long rows = 2;
long long columns = 3;
अपेक्षित आउटपुट:
long long expected = 10;इनपुट:
long rows = 2;
long columns = 3;
अपेक्षित आउटपुट:
long expected = 10;व्याख्या
Every route contains five moves. Choosing which two are down gives ten distinct routes.
इनपुट:
rows = 0
columns = 4
अपेक्षित आउटपुट:
expected = 1इनपुट:
long long rows = 0;
long long columns = 4;
अपेक्षित आउटपुट:
long long expected = 1;इनपुट:
long rows = 0;
long columns = 4;
अपेक्षित आउटपुट:
long expected = 1;व्याख्या
There is only the straight route of four right moves.
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Each route is just an ordering of the required down and right moves.
संकेत 2
Count how many ways to choose the positions of one move type among all moves, rather than exploring paths one by one.
संकेत 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.
अपेक्षित जटिलता
O(min(rows, columns)) time, O(1) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।