Skip to content

Latest commit

 

History

History
145 lines (95 loc) · 5.13 KB

dynamic.md

File metadata and controls

145 lines (95 loc) · 5.13 KB
Raw

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

Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.

Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы. Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

Составляющие:

  • Состояние
  • Ответ
  • База
  • Формула
  • Последовательность

Задача "Кузнечик"

Перед клетчатой полоской длины n сидит кузнечик. В каждой клетке написано целое число. Когда кузнечик оказывается в какой-то клетке, ему дают конфет в том количестве, которое записано в этой клетке. Кузнечик умеет прыгать на следующую ступеньку, а также через одну. Помогите кузнечику - определите, какое максимальное количество конфет он может съесть, если в итоге кузнечик должен оказаться в последней клетке? Обратите внимание, количество конфет может быть отрицательно.

Входные данные

В первой стркое записано единственное целое число n (1<= n<= 10^5) - длина полоски.

Во второй строке записано n целых чисел ai (-10^9 <= ai <= 10^9) - количество конфет в каждой клетке.

Выходные данные

Выведите одно число - максимальное количество конфет, которое может собрать кузнечик.

Решение

Составляющие:

  • Состояние: пусть di - максимальное количество собрыннх конфет в ячейке i

  • Ответ: d[n]

  • База: d[0] = 0; d[1] = число из mas[1]

  • Формула: d[i]= max(d[i-1], d[i-2]) + mas[i]

  • Последовательность: i по возрастанию

#include <bits/stdc++.h>
using namespace std;

#define ios_b                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

typedef long long ll;
typedef long double ld;

const int MAXARR = 1e5 + 5;
ll mas[MAXARR];
ll dp[MAXARR];

void solve()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> mas[i];

    dp[0] = 0;
    dp[1] = mas[1];

    for (int i = 2; i <= n; ++i)
        dp[i] = max(dp[i - 1], dp[i - 2]) + mas[i];

    cout << dp[n] << endl;
}

int main()
{
    ios_b;
    solve();
    return 0;
}

Задача "Строка Фибоначчи"

Строкой Фибоначчи называется строка, состоящая только из 0 и 1, в которой не встречается двух 1 подряд. Вам требуется найти количество таких строк длины n.

Входные данные

Во входных данных записано одно число n (0 <= n <= 90) - длина строки

Выходные данные

Выведите одно число - количество строк Фибоначчи длины n.

Решение

Составляющие:

  • Состояние: пусть d[i] - количество строк Фибоначчи длины i

  • Ответ: d[n]

  • База: dp[0] = 1 (для пустой строки), dp[1] = 2 ("0" и "1")

  • Формула: d[i]= d[i-1] + d[i-2]

  • Последовательность: i по возрастанию

#include <bits/stdc++.h>
using namespace std;

#define ios_b                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

typedef long long ll;
typedef long double ld;

const int MAXARR = 91;
ll dp[MAXARR];

void solve()
{
    int n;
    cin >> n;

    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i <= n; ++i)
        dp[i] = dp[i - 1] + dp[i - 2];

    cout << dp[n] << endl;
}

int main()
{
    ios_b;
    solve();
    return 0;
}