Доброго времени суток! ****
Не так давно начал прорешивать задачи на жадные алгоритмы и ДП. Очень часто затрудняюсь доказывать оптимальность своих решений.
Собственно вопрос: Существует ли общая схема построения доказательства жадных алгоритмов и решений ДП?
Заранее спасибо.
Общих методов конечно нет. Но для жадных алгоритмов существует теория матроидов, которая позволяет многое доказать (хотя часто намного проще доказать без матроидов). А ДП с точки зрения математики это просто мат. индукция: есть база для которой ответ считается на листочке (в редких случаях база это отдельная задача, которая например может быть решена динамикой) и переходы.
Тут тоже были обсуждения на эту тему.