Chapter 26 of 30
Dynamic Programming — Foundations
Master the DP paradigm, the DP recipe, classic DP problems, LIS, and Kadane's algorithm.
The DP ParadigmThe DP RecipeClassic DP ProblemsLongest Increasing Subsequence (LIS)Maximum Subarray Sum (Kadane's Algorithm)
Share:
Dynamic Programming — Foundations
DP is the most important algorithmic paradigm in competitive programming. If you can identify a DP problem and implement it, you can solve a huge fraction of contest problems.
The DP Paradigm
DP works when a problem has:
- Optimal substructure: the optimal solution contains optimal solutions to subproblems
- Overlapping subproblems: the same subproblems are solved multiple times
Instead of recomputing, store the results of subproblems.
The DP Recipe
- Define the state: what does
dp[i](ordp[i][j]) represent? - Write the recurrence: how does
dp[i]depend on smaller subproblems? - Identify base cases: what are the trivial subproblems?
- Determine the order: compute states from smallest to largest
- Extract the answer: which state(s) give the final answer?
Classic DP Problems
Fibonacci Numbers
hljs cpp
// dp[i] = i-th Fibonacci number
vector<long long> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
// Space-optimized:
long long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
long long c = a + b;
a = b;
b = c;
}
Climbing Stairs
hljs cpp
// dp[i] = number of ways to reach step i
dp[0] = 1; // one way: don't move
dp[1] = 1; // one way: one step
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
House Robber
hljs cpp
// dp[i] = max money robbed from houses 0..i
dp[0] = a[0];
dp[1] = max(a[0], a[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);
}
Longest Increasing Subsequence (LIS)
O(n²) DP
hljs cpp
// dp[i] = length of LIS ending at index i
vector<int> dp(n, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int lis = *max_element(dp.begin(), dp.end());
O(n log n) with Binary Search
hljs cpp
vector<int> tails; // tails[i] = smallest tail of all increasing subsequences of length i+1
for (int x : a) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) {
tails.push_back(x); // extend
} else {
*it = x; // replace
}
}
int lis = tails.size();
Reconstruct LIS
hljs cpp
vector<int> tails;
vector<int> parent(n, -1); // for reconstruction
vector<int> tailIndices; // indices corresponding to tails
for (int i = 0; i < n; i++) {
auto it = lower_bound(tails.begin(), tails.end(), a[i]);
int pos = it - tails.begin();
if (it == tails.end()) {
tails.push_back(a[i]);
tailIndices.push_back(i);
} else {
*it = a[i];
tailIndices[pos] = i;
}
parent[i] = (pos > 0) ? tailIndices[pos - 1] : -1;
}
// Reconstruct
vector<int> lis;
int cur = tailIndices[tails.size() - 1];
while (cur != -1) {
lis.push_back(a[cur]);
cur = parent[cur];
}
reverse(lis.begin(), lis.end());
Maximum Subarray Sum (Kadane's Algorithm)
hljs cpp
long long maxSum = a[0], currentSum = a[0];
for (int i = 1; i < n; i++) {
currentSum = max((long long)a[i], currentSum + a[i]);
maxSum = max(maxSum, currentSum);
}
Kadane's with Subarray Indices
hljs cpp
long long maxSum = a[0], currentSum = a[0];
int start = 0, end = 0, tempStart = 0;
for (int i = 1; i < n; i++) {
if (a[i] > currentSum + a[i]) {
currentSum = a[i];
tempStart = i;
} else {
currentSum += a[i];
}
if (currentSum > maxSum) {
maxSum = currentSum;
start = tempStart;
end = i;
}
}
// Maximum subarray is a[start..end]
Circular Maximum Subarray Sum
hljs cpp
// Case 1: Normal Kadane's
long long normal = kadane(a);
// Case 2: Circular (wrap-around)
long long total = accumulate(a.begin(), a.end(), 0LL);
for (int &x : a) x = -x;
long long inverted = kadane(a);
long long circular = total + inverted;
long long answer = max(normal, circular);
Summary
- DP state: define what dp[i] or dp[i][j] means
- Recurrence: express dp[i] in terms of smaller subproblems
- Base cases: the trivial cases that start the computation
- LIS: O(n²) DP or O(n log n) with binary search on tails
- Kadane's: O(n) maximum subarray sum — the most-asked DP
- Space optimization: if dp[i] only depends on dp[i-1], keep only two variables
Prefer reading offline? Download the full book as a PDF.
Download Free Book