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

Recursive Backtracking & Top-Down DP (Memoization)

▼


// 1. Standard Recursive Backtracking Template (Combinatorial Search)
void backtrack(int index, State& current, vector& results) {
    if (is_valid_solution(current)) {
        results.push_back(current);
        // return; // Uncomment if searching for a single solution
    }

    for (const auto& candidate : get_candidates(index, current)) {
        if (is_valid_choice(candidate, current)) {
            make_choice(candidate, current);          // Choose
            backtrack(index + 1, current, results);  // Recurse
            undo_choice(candidate, current);          // Backtrack
        }
    }
}

// 2. Backtracking + Memoization Template (Top-Down Dynamic Programming)
// Useful when subproblems overlap (e.g., Target Sum, Combination Sum)
int memo[MAX_INDEX][MAX_STATE];

int dfs(int index, int state) {
    if (base_case(index, state)) return base_value;
    if (memo[index][state] != -1) return memo[index][state]; // Return cached result

    int res = 0;
    for (const auto& next_state : get_next_states(index, state)) {
        res += dfs(index + 1, next_state);
    }

    return memo[index][state] = res; // Cache and return
}

1. (78) Subsets

Spoiler & Solution

Spoiler: At each index, decide whether to include or exclude the current element, or loop over starting positions to generate all subset combinations.


class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        
        auto dfs = [&](auto& self, int start) -> void {
            res.push_back(path);
            for (int i = start; i < nums.size(); ++i) {
                path.push_back(nums[i]);
                self(self, i + 1);
                path.pop_back();
            }
        };
        
        dfs(dfs, 0);
        return res;
    }
};

2. (17) Letter Combinations of a Phone Number

Spoiler & Solution

Spoiler: Map each digit to its corresponding letter string. Recurse index-by-index through the digits, building combinations character by character.


class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        vector<string> pad = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        vector<string> res;
        string current;

        auto backtrack = [&](auto& self, int idx) -> void {
            if (idx == digits.size()) {
                res.push_back(current);
                return;
            }
            for (char c : pad[digits[idx] - '0']) {
                current.push_back(c);
                self(self, idx + 1);
                current.pop_back();
            }
        };

        backtrack(backtrack, 0);
        return res;
    }
};

3. (46) Permutations

Spoiler & Solution

Spoiler: Swap the current element with all subsequent elements to fix choices in place without requiring additional memory for a visited array.


class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;

        auto backtrack = [&](auto& self, int start) -> void {
            if (start == nums.size()) {
                res.push_back(nums);
                return;
            }
            for (int i = start; i < nums.size(); ++i) {
                swap(nums[start], nums[i]);
                self(self, start + 1);
                swap(nums[start], nums[i]);
            }
        };

        backtrack(backtrack, 0);
        return res;
    }
};

4. (77) Combinations

Spoiler & Solution

Spoiler: Select $k$ elements from 1 to $n$. Optimize by pruning branches where the remaining elements are fewer than needed to reach size $k$.


class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;

        auto backtrack = [&](auto& self, int start) -> void {
            if (path.size() == k) {
                res.push_back(path);
                return;
            }
            // Pruning: Stop if remaining numbers aren't enough to reach size k
            for (int i = start; i <= n - (k - path.size()) + 1; ++i) {
                path.push_back(i);
                self(self, i + 1);
                path.pop_back();
            }
        };

        backtrack(backtrack, 1);
        return res;
    }
};

5. (39) Combination Sum

Spoiler & Solution

Spoiler: Elements can be reused infinitely; when recursing down, stay at index i instead of moving to i + 1. Stop early if remaining sum < 0.


class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> path;

        auto backtrack = [&](auto& self, int start, int remain) -> void {
            if (remain == 0) {
                res.push_back(path);
                return;
            }
            for (int i = start; i < candidates.size(); ++i) {
                if (candidates[i] <= remain) {
                    path.push_back(candidates[i]);
                    self(self, i, remain - candidates[i]); // Note: Pass 'i' to allow element reuse
                    path.pop_back();
                }
            }
        };

        backtrack(backtrack, 0, target);
        return res;
    }
};

6. (494) Target Sum

Spoiler & Solution

Spoiler: Each element can be assigned + or -. Because subproblems repeat for state (index, current_sum), top-down memoization drastically improves efficiency.


class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        unordered_map<string, int> memo;

        auto dfs = [&](auto& self, int idx, int curr_sum) -> int {
            if (idx == nums.size()) {
                return curr_sum == target ? 1 : 0;
            }
            string key = to_string(idx) + "," + to_string(curr_sum);
            if (memo.count(key)) return memo[key];

            int add = self(self, idx + 1, curr_sum + nums[idx]);
            int sub = self(self, idx + 1, curr_sum - nums[idx]);

            return memo[key] = add + sub;
        };

        return dfs(dfs, 0, 0);
    }
};

7. (491) Non-decreasing Subsequences

Spoiler & Solution

Spoiler: To avoid generating duplicate subsequences without sorting the input array, use a local unordered_set within each recursion level to track used elements.


class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;

        auto backtrack = [&](auto& self, int start) -> void {
            if (path.size() >= 2) {
                res.push_back(path);
            }
            unordered_set<int> used;
            for (int i = start; i < nums.size(); ++i) {
                if (used.count(nums[i])) continue;
                if (path.empty() || nums[i] >= path.back()) {
                    used.insert(nums[i]);
                    path.push_back(nums[i]);
                    self(self, i + 1);
                    path.pop_back();
                }
            }
        };

        backtrack(backtrack, 0);
        return res;
    }
};

8. (79) Word Search (Rat in a Maze inspired)

Spoiler & Solution

Spoiler: Explore 4 directions from each cell. In-place grid marking (e.g., set visited cell to '#') saves memory without requiring a separate 2D visited array.


class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();

        auto dfs = [&](auto& self, int r, int c, int idx) -> bool {
            if (idx == word.size()) return true;
            if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[idx]) return false;

            char temp = board[r][c];
            board[r][c] = '#'; // Mark visited

            bool found = self(self, r + 1, c, idx + 1) ||
                         self(self, r - 1, c, idx + 1) ||
                         self(self, r, c + 1, idx + 1) ||
                         self(self, r, c - 1, idx + 1);

            board[r][c] = temp; // Backtrack
            return found;
        };

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dfs(dfs, i, j, 0)) return true;
            }
        }
        return false;
    }
};

9. (22) Generate Parentheses

Spoiler & Solution

Spoiler: Track open and close bracket counts. Add '(' if open < n, and add ')' only if close < open to preserve validity.


class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string current;

        auto backtrack = [&](auto& self, int open, int close) -> void {
            if (current.size() == 2 * n) {
                res.push_back(current);
                return;
            }
            if (open < n) {
                current.push_back('(');
                self(self, open + 1, close);
                current.pop_back();
            }
            if (close < open) {
                current.push_back(')');
                self(self, open, close + 1);
                current.pop_back();
            }
        };

        backtrack(backtrack, 0, 0);
        return res;
    }
};

10. (51) N-Queens (N = 8 has 92 solutions!)

Spoiler & Solution

Spoiler: Place queens row-by-row. Maintain boolean arrays for occupied columns and diagonals (row - col + n and row + col) for $O(1)$ safety checks.


class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        vector<bool> cols(n, false), diag1(2 * n, false), diag2(2 * n, false);

        auto backtrack = [&](auto& self, int r) -> void {
            if (r == n) {
                res.push_back(board);
                return;
            }
            for (int c = 0; c < n; ++c) {
                int d1 = r - c + n, d2 = r + c;
                if (cols[c] || diag1[d1] || diag2[d2]) continue;

                board[r][c] = 'Q';
                cols[c] = diag1[d1] = diag2[d2] = true;

                self(self, r + 1);

                board[r][c] = '.';
                cols[c] = diag1[d1] = diag2[d2] = false;
            }
        };

        backtrack(backtrack, 0);
        return res;
    }
};

11. (37) Sudoku Solver

Spoiler & Solution

Spoiler: Find the first empty cell, try digits '1' to '9', check row/col/box constraints, and recurse. Return true immediately when a solution is completed to stop further exploration.


class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        auto isValid = [&](int r, int c, char ch) {
            for (int i = 0; i < 9; ++i) {
                if (board[r][i] == ch) return false;
                if (board[i][c] == ch) return false;
                if (board[3 * (r / 3) + i / 3][3 * (c / 3) + i % 3] == ch) return false;
            }
            return true;
        };

        auto solve = [&](auto& self) -> bool {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    if (board[i][j] == '.') {
                        for (char ch = '1'; ch <= '9'; ++ch) {
                            if (isValid(i, j, ch)) {
                                board[i][j] = ch;
                                if (self(self)) return true;
                                board[i][j] = '.';
                            }
                        }
                        return false; // Backtrack if no digit fits
                    }
                }
            }
            return true; // Sudoku fully solved
        };

        solve(solve);
    }
};

Explorer of Infinity

Search This Blog