mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-03-13 09:50:19 +08:00
a2efba59bf
* Add euler project problem 15 additional solution by explicitly counting the paths. * Update sol2.py * updating DIRECTORY.md * updating DIRECTORY.md * Trigger CI * [pre-commit.ci] auto fixes from pre-commit.com hooks for more information, see https://pre-commit.ci --------- Co-authored-by: Maxim Smolskiy <mithridatus@mail.ru> Co-authored-by: MaximSmolskiy <MaximSmolskiy@users.noreply.github.com> Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
33 lines
733 B
Python
33 lines
733 B
Python
"""
|
|
Problem 15: https://projecteuler.net/problem=15
|
|
|
|
Starting in the top left corner of a 2x2 grid, and only being able to move to
|
|
the right and down, there are exactly 6 routes to the bottom right corner.
|
|
How many such routes are there through a 20x20 grid?
|
|
"""
|
|
|
|
|
|
def solution(n: int = 20) -> int:
|
|
"""
|
|
Solve by explicitly counting the paths with dynamic programming.
|
|
|
|
>>> solution(6)
|
|
924
|
|
>>> solution(2)
|
|
6
|
|
>>> solution(1)
|
|
2
|
|
"""
|
|
|
|
counts = [[1 for _ in range(n + 1)] for _ in range(n + 1)]
|
|
|
|
for i in range(1, n + 1):
|
|
for j in range(1, n + 1):
|
|
counts[i][j] = counts[i - 1][j] + counts[i][j - 1]
|
|
|
|
return counts[n][n]
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print(solution())
|