Динамическое программирование

Рассмотрим вариант решения:

❓Необходимо вычислить сумму n чисел: 1 + 2 + 3 + … + n

«Сложность» данной задачи состоит в необходимости сразу взять большое количество чисел.

✅ Попробуем разбить на простые подзадачи.

Начнем с суммы одного первого элемента, т.е просто берем первый элемент:

F(1)=1

Тогда с помощью первого элемента найдем второй. К сумме первого добавляем второй элемент:

F(2)=F(1)+2=1+2=3;
F(3)=F(2)+3=3+3=6;

по аналогии продолжаем дальше и получаем функцию, по которой наши значения вычисляются:
➡️ F(n)=F(n-1)+F(n)

Мы определили порядок и поделили задачу на подзадачу, затем решили каждую из них, опираясь на промежуточный результат.

🧑‍💻 Такой пример показывает идею динамического программирования.