Задача на динамическое программирование

Question

Я только недавно начал изучать динамическое программирование. Не совсем понимаю как решать такие задачи. Статей на эту тему в интернете очень мало. Можете объяснить принцип решения задачи от начала до конца? Вот задача: Игровое поле N×M заполняется целыми числами, одно неотрицательное целое число в каждой клетке. Цель игры состоит в том, чтобы пройти по любому разрешенному пути от верхнего левого угла до правого нижнего. Целое число в каждой клетке указывает, какой длины шаг должен быть из текущей клетки. Все шаги могут быть или направо или вниз. Если в результате какого-либо шага игрок покидает пределы поля, такой шаг запрещается.

Требуется написать программу, которая определит число различных вариантов путей от верхнего левого угла до правого нижнего. Объясните пожалуйста. Язык python.

Answer 1

Давайте построим ориентированный граф, где вершины это клетки, а ребро из v в u есть только тогда из v можно перейти в u.

Теперь у нас есть ориентированный граф без циклов. Без циклов он будет, т.к при каждом ходе хотя бы одна координата растет(чтобы это условие выполнялось следует игнорировать нули в таблице).

Посчитать в нем количество путей - стандартная задача. Ответом для вершины x будет сумма по ответам всех вершин y, таких что из y есть ребро в x.

Базой динамики будет, то что в клетку (1, 1) есть только один способ попасть.

Динамику можно пересчитывать проходясь по таблице сверху-вниз слева-направо.

table = [[1, 2, 1],
         [1, 3, 1],
         [2, 1, 1]] # изначальная таблица


n, m = 3, 3 # размеры таблицы
graph_from = [[[] for _ in range(m)] for _ in range(n)]

dirs = [(1, 0), (0, 1)]

for i in range(n):
    for j in range(m):
        if table[i][j] == 0:
            continue
        for k in dirs:
            to_i = i + k[0] * table[i][j]
            to_j = j + k[1] * table[i][j]
            if 0 <= to_i < n and 0 <= to_j < m:
                graph_from[to_i][to_j].append((i, j))

dp = [[0 for _ in range(m)] for _ in range(n)]

dp[0][0] = 1

for i in range(n):
    for j in range(m):
        for x, y in graph_from[i][j]:
            dp[i][j] += dp[x][y]
ans = dp[n - 1][m - 1]
print(ans)

БЛОГ НА HUSL

Задача на динамическое программирование

Ответы (1 шт):