Динамическое программирование: баяны

Есть ряд классических задач на динамическое программирование, которые хорошо бы знать наизусть. Большинство этих задач разобраны в теории про ДП на уровне 2. В контесте ниже, помимо этих баянов, есть еще несколько интересных задач на ДП.