Đề bài
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.
Ràng buộc
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.
Ví dụ
Đầu vào:
rows = 2
columns = 3
Kết quả mong đợi:
expected = 10Đầu vào:
long long rows = 2;
long long columns = 3;
Kết quả mong đợi:
long long expected = 10;Đầu vào:
long rows = 2;
long columns = 3;
Kết quả mong đợi:
long expected = 10;Giải thích
Every route contains five moves. Choosing which two are down gives ten distinct routes.
Đầu vào:
rows = 0
columns = 4
Kết quả mong đợi:
expected = 1Đầu vào:
long long rows = 0;
long long columns = 4;
Kết quả mong đợi:
long long expected = 1;Đầu vào:
long rows = 0;
long columns = 4;
Kết quả mong đợi:
long expected = 1;Giải thích
There is only the straight route of four right moves.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Each route is just an ordering of the required down and right moves.
Gợi ý 2
Count how many ways to choose the positions of one move type among all moves, rather than exploring paths one by one.
Gợi ý 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.
Độ phức tạp mong đợi
O(min(rows, columns)) time, O(1) extra space
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.