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

Редакция Без Сменки
Честно. Понятно. С душой.
📄 Динамическое программирование — это способ решения сложных задач путем сведения их к более простым задачам того же типа.

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

❓Необходимо вычислить сумму 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)

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

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

Где вы учитесь?

Вам также будет интересно

Климатограммы в таблицах
Субтропический муссонный пояс Субарктический пояс Умеренный резко-континентальный...
Законодательство РФ о выборах
В России путём выборов избираются: • Президент РФ • Государственная Дума РФ • представительные...
БИНАРНЫЕ ФУНКЦИИ
Логических функций от одного аргумента всего 4. 👉 Бинарные функции (иногда их еще называют...
Рекурсивные алгоритмы
Разобрали тему рекурсивных алгоритмов и сделали удобные шпаргалки. Готовимся к ЕГЭ по информатике с...
Сумчатые и их особенности
Когда кто-то говорит про сумчатых животных, а это целый инфракласс, то в голове всегда всплывает...
Механические волны
Что такое «волна» в физике? Назовём её кратко процессом распространения колебаний в среде. ...

0 комментария

Авторизуйтесь, чтобы оставить комментарий.