Задача
Дано:
- F(1)=1 при n <= 1
- F(n)=n+F(n−1) при n>1
- n - натуральное число
Найти: F(2023)−F(2020)
Решение динамическим программированием. Разбор
Принцип: Заполнение таблицы "снизу вверх", сохраняя промежуточные результаты
Формула перехода: F(i)=i+F(i−1)
Заполнение таблицы:
| n |
F(n) |
Формула |
| 1 |
1 |
базовое значение |
| 2 |
3 |
2 + 1 = 3 |
| 3 |
6 |
3 + 3 = 6 |
| 4 |
10 |
4 + 6 = 10 |
| ... |
... |
... |
| 2020 |
F(2020) |
2020 + F(2019) |
| 2021 |
F(2021) |
2021 + F(2020) |
| 2022 |
F(2022) |
2022 + F(2021) |
| 2023 |
F(2023) |
2023 + F(2022) |
Заполнение таблицы на языке Python