Количество путей в матрице

Количество путей в матрице

Это классическая задача динамического программирования. Робот должен пройти из верхнего левого угла в нижний правый, может двигаться только вправо или вниз. Нужно найти количество уникальных путей.

Математический подход

Для сетки m×n:

• Робот начинает в (0, 0)
• Финиш в (m-1, n-1)
• Всего нужно сделать (m-1) шагов вниз и (n-1) шагов вправо
• Общее количество шагов: (m-1) + (n-1) = m + n - 2

Задача сводится к: сколько способов выбрать (m-1) позиций из (m+n-2) позиций для шагов вниз?

Это комбинаторика: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)

Пример: матрица 3×2
Шаги: вниз, вниз (2 шага вниз), вправо (1 шаг вправо)
Общо: 3 шага

Комбинации:
- ВВП (вниз, вниз, вправо)
- ВПВ (вниз, вправо, вниз)
- ПВВ (вправо, вниз, вниз)

Итого: 3 пути = C(3, 2) = 3

Решение 1: Комбинаторная формула (O(m+n))

def unique_paths_math(m, n):
    from math import factorial
    return factorial(m + n - 2) // (factorial(m - 1) * factorial(n - 1))

print(unique_paths_math(3, 2))  # 3
print(unique_paths_math(3, 7))  # 28

Решение 2: Динамическое программирование (O(m×n))

Создаём таблицу, где dp[i][j] количество путей до ячейки (i, j).

def unique_paths_dp(m, n):
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    
    return dp[m - 1][n - 1]

Пошаговое выполнение (m=3, n=2)

Матрица 3×2:

Инициализация (первый ряд и столбец):
dp[0][0] = 1, dp[0][1] = 1
dp[1][0] = 1, dp[2][0] = 1

  j=0  j=1
i=0 1    1
i=1 1    ?

Заполнение:
dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2

  j=0  j=1
i=0 1    1
i=1 1    2
i=2 1    ?

dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3

Результат: 3

Оптимизация памяти (O(n))

def unique_paths_optimized(m, n):
    dp = [1] * n
    
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j - 1]
    
    return dp[n - 1]

Полная реализация

def unique_paths_all_methods(m, n):
    # Способ 1: Комбинаторика
    def method1():
        from math import factorial
        return factorial(m + n - 2) // (factorial(m - 1) * factorial(n - 1))
    
    # Способ 2: DP с таблицей 2D
    def method2():
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]
    
    # Способ 3: DP с оптимизацией памяти
    def method3():
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
        return dp[n - 1]
    
    # Способ 4: Рекурсия с мемоизацией
    def method4():
        memo = {}
        
        def dp(i, j):
            if (i, j) in memo:
                return memo[(i, j)]
            if i == 0 or j == 0:
                return 1
            memo[(i, j)] = dp(i - 1, j) + dp(i, j - 1)
            return memo[(i, j)]
        
        return dp(m - 1, n - 1)
    
    return {
        "Комбинаторика": method1(),
        "DP 2D": method2(),
        "DP оптимизировано": method3(),
        "Рекурсия + мемо": method4()
    }

print(unique_paths_all_methods(3, 2))
print(unique_paths_all_methods(3, 7))

Визуализация DP таблицы (3×7)

  1  2  3  4  5  6  7
1 1  1  1  1  1  1  1
2 1  2  3  4  5  6  7
3 1  3  6  10 15 21 28

Сравнение методов

Эта задача показывает мощь динамического программирования для оптимизации экспоненциальных проблем.