Уравнение Беллмана придает определенную форму динамическим c программным решениям и, используя их, мы можем обобщать решения оптимизационных задач, которые являются рекурсивными по природе и следуют свойству оптимальная подструктура .
Оптимальная подструктура в более простых терминах означает, что данная проблема может быть разбита на более мелкие подзадачи, которые требуют того же решения с меньшими данными. Если может быть вычислено оптимальное решение меньшей задачи, то это означает, что данная задача (более крупная) также может быть вычислена.
Обозначим решение задачи для данного состояния S значением V(S), S - это состояние или подзадача. Давайте обозначим стоимость, которую понесем, выбрав действие a(i) в состоянии S, равное R. R будет функцией f(S, a(i)), где a - набор всех возможных действий, которые можно выполнить в состоянии S.
V(S) = max{ f(S, a(i)) + y * V(S') }, где max берется путем итерации все возможно i. y является фиксированной константой, которая облагает подзадачей переход к большей проблеме, для большинства проблем y = 1, поэтому вы можете пока игнорировать ее.
Таким образом, в принципе, для любой данной подзадачи S, V(S) даст нам наиболее оптимальное решение, выбрав все комбинации действий a(i), которые можно выполнить, и следующее состояние, которое будет создано с помощью это действие. Если вы мыслите рекурсивно и привыкли к таким вещам, то легко понять, почему приведенное выше уравнение является правильным.
Я бы предложил решить задачи динамического программирования c и посмотреть на некоторые стандартные проблемы и способы их решения, чтобы получить идея, как эти проблемы разбиваются на более мелкие похожие проблемы и решаются рекурсивно. После этого приведенное выше уравнение будет иметь больше смысла. Кроме того, вы поймете, что два уравнения, которые вы написали выше, - это почти одно и то же, просто они написаны немного по-другому.
Здесь - это список наиболее известных проблем DP и их решения.