🎯Задача. Уникальные тропы
Сложность задачи: Medium.
Условие задачи: дано поле размером m x n. Изначально робот находится в левом верхнем углу. Необходимо посчитать сколькими возможными уникальными путями робот может добраться в правый нижний угол.
Робот может двигаться лишь вправо и вниз.
Пример:
Ввод: m = 3, n = 7
Вывод: 28.
Решение:
Ваше мнение пишите в комментариях 👇
@python_job_interview
Сложность задачи: Medium.
Условие задачи: дано поле размером m x n. Изначально робот находится в левом верхнем углу. Необходимо посчитать сколькими возможными уникальными путями робот может добраться в правый нижний угол.
Робот может двигаться лишь вправо и вниз.
Пример:
Ввод: m = 3, n = 7
Вывод: 28.
Решение:
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# Purpose: find # ways to go from top-left to bottom-right
# Formula: res[i][j] += res[all i][j - 1]
# build
dp = [0] * n
dp[0] = 1
# find
for i in range(m):
for j in range(n):
if j >= 1:
dp[j] += dp[j - 1]
# return
return dp[-1]Ваше мнение пишите в комментариях 👇
@python_job_interview