Linear DP

Core Concepts

Dynamic Programming (DP) solves complex problems by breaking them in to overlapping subproblems. The solution to the main problem is derived from solutions to these subproblems.

State Representation

State are typically represented as dp[i][j] = value, where i and j are indices or variables describing the state, and value is the state's computed result.

State Transition

This defines the relationship between states, usualy expressed as a mathematical formula that determines the direction of iteration or recursion.

Final State

The ultimate solution to the problem.

Implementation Steps

1. Define States: Typically represents counts, minimum costs, or maximum values up to a certain point.
2. Establish Transition Equations: Formulas to derive new states from existing ones, determining whether to use iteration or recursion.
3. Determine Final State: The output solution.

Example: Number Triangle

State transition equation: dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j]

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N][N], dp[N][N];

int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j)
            cin >> a[i][j];

    for (int i = n; i >= 1; --i)
        for (int j = 1; j <= i; ++j)
            dp[i][j] = a[i][j] + max(dp[i+1][j], dp[i+1][j+1]);

    cout << dp[1][1] << '\n';
    return 0;
}

Two-Dimensional DP

Extends DP concepts to multiple dimensions.

Example: Building Houses

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int dp[55][2000];

int main() {
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i <= k; i++) dp[0][i] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int x = i-1; x <= k-1; x++)
                dp[i][j+x] = (dp[i-1][x] + dp[i][j+x]) % mod;

    cout << dp[n][k] << '\n';
    return 0;
}

Longest Increasing Subsequence (LIS)

Model

O(n^2) time complexity. dp[i] represents the length of the longest increasing subsequence ending at a[i].

Transition equation: dp[i] = max(dp[i], dp[j] + 1) if a[i] > a[j]

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int num[N], dp[N];

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

    for (int i = 1; i <= n; ++i) {
        dp[i] = 1;
        for (int j = 1; j < i; ++j)
            if (num[i] > num[j])
                dp[i] = max(dp[i], dp[j]+1);
    }

    int ans = *max_element(dp+1, dp+n+1);
    cout << ans << '\n';
    return 0;
}

Longest Common Subsequence (LCS)

Model

O(n^2) time complexity. dp[i][j] represents the LCS length of sequences A[1..i] and B[1..j].

Transition equations:

• If a[i] == b[j]: dp[i][j] = dp[i-1][j-1] + 1
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int a[N], b[N], dp[N][N];

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

    cout << dp[n][m] << '\n';
    return 0;
}