Overview

Linear dynamic programming is one of the most fundamental types of DP problems. Instead of a lengthy introduction, the key is to solve many problems to develop intuition.

Basic Steps

• State Definition: Define dp[i] as the optimal solution (maximum, minimum, count of ways, etc.) for the first i elements.
• State Transition: Derive the current state from previous states and write the recurrence.

Once these two steps are correctly performed, the problem can be solved efficiently.

Space Optimization

By examining the transition equation, we often find that only a few previous values are needed for computation, allowing us to reduce memory usage—especially useful for large datasets.

Longest Increasing Subsequence (LIS)

Given an array arr of length n, find the length of the longest strictly increasing subsequence.

Let dp[i] represent the length of the longest increasing subsequence ending at arr[i].

Recurrence relation: dp[i] = max(dp[j] + 1) for all j < i and arr[j] < arr[i]

Explanation: We define dp[i] as the maximum length among all strictly increasing subsequences whose last element is arr[i]. To build a subsequence ending at arr[i], we can extend any subsequence ending at a previous arr[j] (where j < i) provided arr[j] < arr[i] to maintain the increasing order.

Thus: dp[i] = max(dp[j] + 1) for all j < i and arr[j] < arr[i]

Proof sketch: For any j where arr[j] < arr[i], the longest subsequence ending at arr[i] can be formed by appending arr[i] to the best subsequence ending at arr[j]. If arr[j] >= arr[i], it cannot precede arr[i] in an increasing subsequence, so it's excluded from consideration.

Initialization: Set dp[i] = 1 for all positions, since each element alone forms a subsequence of length 1.

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

const int MAXN = 1e5;
int n, arr[MAXN], dp[MAXN];

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        dp[i] = 1;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
    cout << *max_element(dp, dp + n);
    return 0;
}

Note: max_element(begin, end) returns an iterator to the largest element in the range; the * dereferences it to get the value.

Time complexity: O(n²)

Greedy + Binary Search Optimization

Since we only need the length of the LIS (not the subsequence itself), we can maintain an array tails where tails[i] stores the smallest possible ending element of an increasing subsequence of length i+1. This ensures we can extend subsequences as much as possible.

Algorithm:

• Initialize an empty tails array.
• For each arr[i]:
  • Use binary search (lower_bound) to find the first position pos where tails[pos] >= arr[i].
  • If such position exists, update tails[pos] = arr[i].
  • Otherwise, append arr[i] to the end of tails.
• The final length of tails is the LIS length.

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

const int MAXN = 1e5;
int n, arr[MAXN], tails[MAXN], len = 0;

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(tails, tails + len, arr[i]) - tails;
        tails[pos] = arr[i];
        if (pos == len) len++;
    }
    cout << len;
    return 0;
}

Practice

B3637 - Longest Increasing Subsequence

Longest Common Subsequence (LCS)

Given two strings A and B, find the length of their longest common subsequence (not necessarily conttiguous, but order must be preserved).

Example: A = "abcde", B = "ace"
LCS = "ace", length = 3
Note: "aec", "eac", "eca", "cea", "cae" are incorrect.

Let n = length of A, m = length of B.
Define dp[i][j] as the length of the LCS of the first i characters of A and the first j charactres of B.

Recurrence: dp[i][j] = dp[i-1][j-1] + 1 if A[i] == B[j],
otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Intuition: If the current characters match, we can extend the LCS by 1. Otherwise, we take the best result from excluding either the current character of A or B.

Case 1: A[i] == B[j]

• Both characters are the same, so they can serve as the last character of the common subsequence.
• Thus dp[i][j] = dp[i-1][j-1] + 1.
• Example: A = "abcd", B = "aecd", i=4, j=4: both end with 'd'. The LCS ending with 'd' is dp[3][3] + 1.

Case 2: A[i] != B[j]

• Characters differ; we cannot include both.
• The LCS may either exclude A[i] (consider dp[i-1][j]) or exclude B[j] (consider dp[i][j-1]).
• Take the maximum: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Example walkthrough: A = "abcde", B = "ace"

Construct a table dp[i][j] for i from 0 to n and j from 0 to m.