Является ли это оптимальное уравнение подструктуры правильным?

Question

Учитывая сетку amxn, заполненную неотрицательными числами, найдите путь снизу справа вверху слева, который минимизирует сумму всех чисел вдоль ее пути.

Мы начинаем с правого нижнего угла или (m, n ) и наша цель - go позиционировать (1,1) или верхний левый угол.

Я просто немного растерялся, и я не знаю, правильно ли я понял, что нисходящий подход - оптимальная подструктура следующее?

CostToMove(i,j) = Min(CostToMove(i-1,j), CostToMove (i, j+1)) + Cost(i,j)

Answer 1

Кажется, у тебя хороший подход. Есть небольшая проблема, которую нужно исправить: CostToMove (i, j+1). Здесь вы идете вправо не влево , так что, я думаю, вы хотели сказать CostToMove (i, j-1)