В подходе «разделяй и властвуй» подзадачи не зависят друг от друга.
Таким образом, перекрывающиеся подзадачи не могут быть использованы.
Определение оптимальной подструктуры в CLRS гласит:
«проблема демонстрирует оптимальную подструктуру, если оптимальное решение проблемы содержит в себе оптимальные решения подзадач».
Знаем ли мы, что решения подзадач с использованием подхода «разделяй и властвуй» являются оптимальными? Если так, я понимаю, что оптимальная подструктура применяется для подхода «разделяй и властвуй».