kz-maxx

RU KZ
← Басты бет

Динамикалық программалауға кіріспе

Рекурсивный метод, memoization және итеративный DP-ға ауыстыру

Динамикалық программалау деген не?

Динамикалық программалау, қысқаша DP — үлкен задачаны бірнеше кіші подзадачаға бөліп шешу әдісі.

Біз кіші подзадачалардың жауабын бір рет есептейміз де, массивте сақтаймыз. Кейін сол жауап керек болса, қайта есептемей, дайын мәнді аламыз.

үлкен задача
↓
кіші подзадачалар
↓
жауаптарды сақтаймыз
↓
финал answer аламыз
DP-ны түсіну үшін алдымен рекурсия арқылы ойлау ыңғайлы. Кейін рекурсияны итеративный DP-ға ауыстырамыз.

DP қашан қолданылады?

  • бірдей подзадачалар көп рет қайталанса
  • бір мәнді бірнеше рет есептеп жатсақ
  • maximum немесе minimum табу керек болса
  • қанша тәсіл бар екенін санау керек болса
  • кішкентай state-тен үлкен state-ке өту болса
  • dp state ойлап табуға болатын болса

DP-ның негізгі идеясы

DP-да көбіне массив қолданамыз: 

dp[i]

Бұл i state үшін жауап.

Мысалы:

dp[i] = алғашқы i элемент үшін жауап
dp[i] = i-ге дейін жету тәсілдерінің саны
dp[i] = i-ге дейін минималды cost
dp[i] = i-ге дейін максималды сумма

Рекурсивный метод

DP-ны көбіне рекурсиядан бастаған оңай.

Біз функция жазамыз: 

f(i)

Бұл функция i state үшін жауап қайтарады.

f(i) = i state үшін answer

Кейін f(i)-ді кіші мәндер арқылы жазамыз: 

f(i) = f(i - 1) + f(i - 2)

Бұл переход деп аталады.

Мысал: Фибоначчи сандары

Фибоначчи сандары:

f(0) = 0
f(1) = 1
f(n) = f(n - 1) + f(n - 2)

Яғни әр сан екі алдыңғы санның суммасына тең.

Обычный рекурсия

int fib(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

Бұл код дұрыс, бірақ өте баяу.

Неге?

fib(5)
fib(4) және fib(3) шақырады
fib(4) тағы fib(3) шақырады
бірдей мәндер көп рет есептеледі

Обычный рекурсия проблемасы

Обычный рекурсия бір state-ті бірнеше рет қайта есептейді.

Мысалы:

fib(6)
fib(5) + fib(4)
fib(4) бірнеше рет есептеледі
fib(3) одан да көп есептеледі
Сондықтан обычный рекурсия Фибоначчи үшін шамамен O(2ⁿ) жұмыс істейді.

Рекурсия + memoization

Бірдей мәнді қайта есептемеу үшін жауапты массивте сақтаймыз. 

int dp[N];

Егер dp[n] бұрын есептелген болса, оны бірден қайтарамыз. 

if (dp[n] != -1) {
    return dp[n];
}

Бұл әдіс memoization деп аталады.

Фибоначчи memoization арқылы

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

const int N = 100010;

int dp[N];

int fib(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    if (dp[n] != -1) {
        return dp[n];
    }

    dp[n] = fib(n - 1) + fib(n - 2);
    return dp[n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < N; i++) {
        dp[i] = -1;
    }

    cout << fib(n);

    return 0;
}

Не өзгерді?

Енді әр fib(i) тек бір рет есептеледі.

fib(5) есептелді → dp[5]-ке сақталды
қайта керек болса → дайын dp[5] аламыз
Метод Уақыт Память
Обычный рекурсия O(2ⁿ) O(n)
Рекурсия + memoization O(n) O(n)

Рекурсияны итеративный DP-ға қалай ауыстырамыз?

Жеңіл алгоритм:

1. f(i) нені білдіретінін түсінеміз
2. f(i)-ді dp[i]-ге ауыстырамыз
3. Базалық жағдайларды dp-ға жазамыз
4. Рекурсивный переходты циклге айналдырамыз
5. dp-ны кіші мәннен үлкен мәнге қарай есептейміз

Қадам 1: рекурсия болды

Басында былай болды: 

int fib(int n) {
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
}

Мұнда state:

fib(n) = n-ші Фибоначчи саны

Қадам 2: f орнына dp

Рекурсивный функция: 

fib(n)

массивке айналады: 

dp[n]

Яғни:

fib(0) → dp[0]
fib(1) → dp[1]
fib(i) → dp[i]

Қадам 3: базалық жағдайлар

Рекурсияда: 

if (n == 0) return 0;
if (n == 1) return 1;

Итеративный DP-да: 

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

Қадам 4: переход

Рекурсияда: 

fib(n) = fib(n - 1) + fib(n - 2)

DP массивте: 

dp[i] = dp[i - 1] + dp[i - 2];

Енді циклмен санаймыз: 

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

Фибоначчи итеративный DP арқылы

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

const int N = 100010;

long long dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

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

    cout << dp[n];

    return 0;
}

Рекурсивный DP vs итеративный DP

Метод Қалай жұмыс істейді? Плюс Минус
Рекурсия + memoization top-down ойлап табу оңай stack overflow болуы мүмкін
Итеративный DP bottom-up тез және стабильный кейде порядок түсіну қиын
Рекурсивный DP — top-down. Итеративный DP — bottom-up.

Мысал 2: баспалдақ

n саты бар. Бір қадамда 1 немесе 2 сатыға көтерілуге болады. n-ші сатыға жетудің қанша тәсілі бар?

State: 

dp[i] = i сатысына жету тәсілдерінің саны

i сатысына келуге болады:

  • i - 1 сатысынан
  • i - 2 сатысынан

Сондықтан: 

dp[i] = dp[i - 1] + dp[i - 2];

Баспалдақ: рекурсивный метод

int ways(int n) {
    if (n == 0) {
        return 1;
    }

    if (n == 1) {
        return 1;
    }

    return ways(n - 1) + ways(n - 2);
}

Мұнда:

ways(0) = 1
ways(1) = 1
ways(n) = ways(n - 1) + ways(n - 2)

Баспалдақ: рекурсия + memoization

const int N = 100010;

long long dp[N];

long long ways(int n) {
    if (n == 0) {
        return 1;
    }

    if (n == 1) {
        return 1;
    }

    if (dp[n] != -1) {
        return dp[n];
    }

    dp[n] = ways(n - 1) + ways(n - 2);
    return dp[n];
}

Баспалдақ: итеративный DP-ға ауыстыру

Рекурсияда: 

ways(n) = ways(n - 1) + ways(n - 2)

Итеративный DP-да: 

dp[i] = dp[i - 1] + dp[i - 2];

Базалық жағдайлар: 

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

Баспалдақ: итеративный реализация

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

const int N = 100010;

long long dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

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

    cout << dp[n];

    return 0;
}

Мысал 3: минималды cost

Баспалдақ бар. Әр сатының cost[i] бағасы бар. Бір қадамда 1 немесе 2 сатыға жүруге болады. n-ге жету үшін минималды cost табу керек.

State: 

dp[i] = i сатысына дейінгі минималды cost

Переход: 

dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);

Минималды cost: рекурсия

int solve(int i) {
    if (i == 1) {
        return cost[1];
    }

    if (i == 2) {
        return cost[2];
    }

    return cost[i] + min(solve(i - 1), solve(i - 2));
}

Бұл обычный рекурсия. Мұнда бірдей мәндер көп рет есептелуі мүмкін.

Минималды cost: memoization

int solve(int i) {
    if (i == 1) {
        return cost[1];
    }

    if (i == 2) {
        return cost[2];
    }

    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = cost[i] + min(solve(i - 1), solve(i - 2));
    return dp[i];
}

Минималды cost: итеративный DP

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

const int N = 100010;

int n;
int cost[N];
int dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
    }

    dp[1] = cost[1];
    dp[2] = cost[2];

    for (int i = 3; i <= n; i++) {
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
    }

    cout << dp[n];

    return 0;
}

DP-да қалай ойлау керек?

Көп DP задачада мына план көмектеседі:

1. Нені табу керек?
2. dp state нені білдіреді?
3. Базалық жағдайлар қандай?
4. dp[i]-ге қалай өтеміз?
5. Қандай тәртіппен есептейміз?
6. Жауап қай жерде жатыр?

DP-ның негізгі типтері

Тип State мысалы Мағынасы
Тәсіл саны dp[i] i-ге жетудің қанша тәсілі бар
Минимум dp[i] i-ге дейін минималды cost
Максимум dp[i] i-ге дейін максималды сумма
2D DP dp[i][j] екі параметр бойынша answer

Рекурсия → итерация: қысқа схема

Рекурсия Итеративный DP
f(i) dp[i]
if (i == 0) return x dp[0] = x
f(i - 1) dp[i - 1]
f(i - 2) dp[i - 2]
return f(i - 1) + f(i - 2) dp[i] = dp[i - 1] + dp[i - 2]
f(n) шақыру answer = dp[n]

Типтік қателер

  • dp[i] нені білдіретінін түсінбеу
  • базалық жағдайларды ұмыту
  • dp[i - 1] дайын болмай тұрып dp[i] санау
  • minimum мен maximum шатастыру
  • dp массивті дұрыс инициализация жасамау
  • рекурсияда memoization қоспау
  • итерацияда цикл тәртібін қате таңдау

Асимптотика

Метод Уақыт Память
Обычный рекурсия көбіне exponential рекурсия тереңдігіне байланысты
Рекурсия + memoization state саны × transition state саны
Итеративный DP state саны × transition state саны
Қарапайым dp[i] және O(1) transition болса, уақыт көбіне O(n).

Қысқа DP шаблон

dp[0] = base_value;

for (int i = 1; i <= n; i++) {
    dp[i] = transition_from_previous_states;
}

cout << dp[n];

Memoization қысқа шаблон

int solve(int i) {
    if (base_case) {
        return base_value;
    }

    if (dp[i] != -1) {
        return dp[i];
    }

    dp[i] = transition;
    return dp[i];
}