Dynamic Programming compilation

Dynamic Programming Compilation

Basic Recurrence Relation (Fibonacci type)

▼

1. Domino and Tromino tiling
2. 552. Student Attendance Record II
3. Dice Combinations (CSES)
4. 1269. Number of Ways to Stay in the Same Place After Some Steps

5. G. Hits Different (*)

Spoiler

Code in python to prevent overflows

  
prev1 = (row - 1) * (row - 2) // 2 + (col - 1) if col > 1 else 0
prev2 = (row - 1) * (row - 2) // 2 + col if col < row else 0
prev3 = (row - 2) * (row - 3) // 2 + (col - 1) if (row > 2 and col > 1 and (col - 1 <= row - 2)) else 0
f[num] = f[prev1] + f[prev2] - f[prev3] + (num * num)

6. B. Kavi on Pairing Duty

Spoiler
dp[n] = dp[n-1] + dp[n-2] + ... + dp[0] + D[n], where D[n] := # divisors of n

a[i+1] constrained on a[i] (=> f[n][d], a[i] taking values 0 to d-1)

▼

Kleinberg Exercises - 4, 10

1. 1220. Count Vowels Permutation
2. 935. Knight Dialer
3. Vacation (Atcoder)
4. Array Description (CSES)
5. Подкрутка II (*)
6. M. Medical Parity

Spoiler
dp[i][j] = min cost over x'[1..i], y'[1..i] such that y[i] == j, j belongs to {0, 1}. Observe that y[i-1] = (y[i] - x[i]) % 2

7. C. Wonderful City

Spoiler

Row and column imbalance are independent.

 
// solving row imbalance
// use b
std::vector<std::array<ll, 2>> dp(n+1);
dp[0][0] = dp[0][1] = 0;
dp[1][0] = 0; dp[1][1] = b[1];
for (int i = 2; i <= n; i++) {
    // dp[i][0] -> not changing ith col
    // checking if ith col equals (i-1)th col before change and after change
    bool check1 = true, check2 = true, check3 = true;
    for (int r = 1; r <= n; r++) {
        if (h[r][i-1] == h[r][i]) check1 = false;
        if (h[r][i-1] + 1 == h[r][i]) check2 = false;
        if (h[r][i-1] == h[r][i] + 1) check3 = false;

        if (!check1 && !check2 && !check3) break;
    }
    dp[i][0] = INF;
    if (check1) dp[i][0] = std::min(dp[i][0], dp[i-1][0]);
    if (check2) dp[i][0] = std::min(dp[i][0], dp[i-1][1]);
    // dp[i][1] -> increasing ith col by 1
    dp[i][1] = INF;
    if (check1) dp[i][1] = std::min(dp[i][1], dp[i-1][1] + b[i]);
    if (check3) dp[i][1] = std::min(dp[i][1], dp[i-1][0] + b[i]);
}

ll row_sum = std::min(dp[n][0], dp[n][1]);

// solving column imbalance
// use a
dp[0][0] = dp[0][1] = 0;
dp[1][0] = 0; dp[1][1] = a[1];
for (int i = 2; i <= n; i++) {
    // dp[i][0] -> not changing ith row
    // checking if ith col equals (i-1)th row before change and after change
    bool check1 = true, check2 = true, check3 = true;
    for (int c = 1; c <= n; c++) {
        if (h[i-1][c] == h[i][c]) check1 = false;
        if (h[i-1][c] + 1 == h[i][c]) check2 = false;
        if (h[i-1][c] == h[i][c] + 1) check3 = false;

        if (!check1 && !check2 && !check3) break;
    }
    dp[i][0] = INF;
    if (check1) dp[i][0] = std::min(dp[i][0], dp[i-1][0]);
    if (check2) dp[i][0] = std::min(dp[i][0], dp[i-1][1]);
    // dp[i][1] -> increasing ith col by 1
    dp[i][1] = INF;
    if (check1) dp[i][1] = std::min(dp[i][1], dp[i-1][1] + a[i]);
    if (check3) dp[i][1] = std::min(dp[i][1], dp[i-1][0] + a[i]);
}

ll col_sum = std::min(dp[n][0], dp[n][1]);

ll total = row_sum + col_sum;
if (total >= INF) std::cout << "-1\n";
else std::cout << total << '\n';

DP on INTERVALS

▼

dp[i][j] = max(dp[i][t] + dp[t+1][j] + f(i, t, j)) for all i <= t < j

Matrix Chain multiplication

RNA Secondary structure using base pair maximization

Single choice DP

▼

dp[j] = max(wj + dp[i], dp[j-1]) -> OBSERVE THAT FOR ALL IS NOT WRITTEN HERE, SO O(N)

Kleinberg Exercises - 1, 2, 11

1. Maximum profit in Job Scheduling
2. Maximum Earnings From Taxi
3. F. Consecutive Subsequence

Spoiler
dp[a[i]] = std::max(dp[a[i]], 1 + dp[a[i] - 1]) store dp as std::map<int, int>
4. E. Three Strings

Spoiler
dp[i][j] = min(dp[i-1][j] + (a[i] != c[i+j]), dp[i][j-1] + (b[j] != c[i+j]))

5. C. Palindrome Basis

Spoiler

 
	for (int i = 0; i < N; i++) {
        if (isPalindrome(i)) palindromes.push_back(i);
    }
    int M = palindromes.size();
    std::vector<std::vector<ll>> dp(N+1, std::vector<ll>(M, 0));
    for (int i = 1; i < M; i++) {
        dp[1][i] = 1;
        dp[0][i] = 1;
    }
    for (int num = 2; num <= N; num++) {
        for (int lim = 1; lim < M; lim++) {
            if (palindromes[lim] > num) dp[num][lim] = dp[num][lim - 1];
            else {
                dp[num][lim] = (dp[num][lim-1] + dp[num - palindromes[lim]][lim]) % MOD;
            }
        }
    }

6. Minimum ascii delete sum for two strings

7. E. Block Sequence

Spoiler

 
            if (i + a[i] < n) dp[i] = min(1 + dp[i+1], dp[i + a[i] + 1]);
            else dp[i] = 1 + dp[i+1];

8. Maximal Square (*)
Count Square Submatrices with All Ones

Spoiler
dp[i][j] = 0 if mat[i][j] == 0 else 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
maxi = max(dp[i][j])
ans1 = maxi * maxi
ans2 = sum(dp[i][j])
9. D. Make Them Equal(*)

Spoiler
apply dp twice

10. H. Don't Blame Me

Spoiler

dp[i][j] = # subsequences using the first i elements that have AND value of j
For the ith element we have the following choices -

Dont choose -> +dp[i-1][j]
Choose -> (a[i] == j) -> +1, or +dp[i-1][j']

 
for (int i = 1; i <= n; i++) {
    for (int j = 63; j >= 0; j--) {
        if (a[i] == j) dp[j][i] = (dp[j][i] + 1) % NUM;
        dp[j & a[i]][i] = (dp[j & a[i]][i] + dp[j][i-1]) % NUM;
        dp[j][i] = (dp[j][i] + dp[j][i-1]) % NUM;
    }
}
ll ans = 0;
for (int i = 0; i < 64; i++) {
    if (__builtin_popcount(i) == k) ans = (ans + dp[i][n]) % NUM;
}

Multi choice DP

▼

dp[j] = min(dp[j], Cij + dp[i]) for all 1 <= i <= j

Segmented least squares

Kleinberg Exercises - 3, 5, 6, 8, 9, 12, 15, 16(**), 17

1. 132. Palindrome Partitioning II
2. E. Sending a Sequence Over the Network

Spoiler
dp[n] = dp[n-bn-1] || dp[n-x-1] where x is such that b[n-x] = x (precompute this x for reducing TC)

3. LIS (longest increasing subsequence) variant

1. Mukhammadali and the Smooth Array

2. B. Orac and Models

Spoiler

 
#include <iostream>
#include <vector>
#include <algorithm>
using ll = long long;
int N = 1e5 + 10;
std::vector<std::vector<int>> divisors(N);
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    for (int i = 1; i < N; i++) {
        for (int j = 2 * i; j < N; j += i) divisors[j].push_back(i);
    }
    int tt; std::cin >> tt;
    while (tt--) {
        int n; std::cin >> n;
        std::vector<ll> s(n+1);
        std::vector<int> dp(n+1, 1);
        for (int i = 1; i < n; i++) std::cin >> s[i];
        for (int i = 2; i <= n; i++) {
            int maxi = 0;
            for (int j : divisors[i]) if (s[j] < s[i]) maxi = std::max(maxi, dp[j]);
            dp[i] = 1 + maxi;
        }
        std::cout << *max_element(dp.begin(), dp.end()) << std::endl;
    }
    return 0;
}

DP on Trees

▼

 
                        
void dfs(int u, int p = -1) {
    dp[u] = base_case;   // initialize
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u] = combine(dp[u], dp[v]);  // merge child info
    }
}

1. A. Parsa's Humongous Tree

Spoiler
Consider only a_v = l_v or r_v
2. F. Tree, TREE!!!

Spoiler
Find relation between LCA and subtree size

Explorer of Infinity

Search This Blog