Core Ideas of Dynamic Programming
Dynamic programming (DP) requires moving beyond memorized templates. The essence is decomposing a problem into overlapping subproblems, defining states, and establishing transition equations. Three fundamental steps drive most DP solutions:
- State definition (what each dp entry represents)
- Table filling and transition derivation
- Implementation based on the transition equation
The second step usually poses the greatest challenge. Practice with recurrence patterns helps build intuition before tackling state design.
Exercise: Translating Recurrence into Code
Recurrence Pattern 1
Consider a typical 0/1 knapsack scenario. The recurrence can be expressed as:
#include <bits/stdc++.h>
using namespace std;
int dp[110][1010], volume, n, cost[110], value[110];
int main() {
scanf("%d%d", &volume, &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &cost[i], &value[i]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < cost[i]; ++j)
dp[i][j] = dp[i-1][j];
for (int j = cost[i]; j <= volume; ++j)
dp[i][j] = max(dp[i-1][j], dp[i-1][j - cost[i]] + value[i]);
}
printf("%d\n", dp[n][volume]);
return 0;
}
Recurrence Pattern 2
A rod-cutting style recurrence:
#include <bits/stdc++.h>
using namespace std;
int best[1010], n, price[1010];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &price[i]);
for (int i = 1; i <= n; ++i)
for (int len = 1; len <= i; ++len)
best[i] = max(best[i], best[i - len] + price[len]);
int queries, queryLen;
scanf("%d", &queries);
while (queries--) {
scanf("%d", &queryLen);
printf("%d\n", best[queryLen]);
}
return 0;
}
Case Study: Flower Arrangement
Given n types of flowers with quantity limits a[i], find the number of ways to select exactly m flowers. We explore solutions at progressively advanced levels.
Level 1: Memoized Search
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105, MOD = 1000007;
int n, m, limit[MAXN], memo[MAXN][MAXN];
int search(int pos, int selected) {
if (selected > m) return 0;
if (selected == m) return 1;
if (pos == n + 1) return 0;
if (memo[pos][selected]) return memo[pos][selected];
int total = 0;
for (int take = 0; take <= limit[pos]; ++take)
total = (total + search(pos + 1, selected + take)) % MOD;
return memo[pos][selected] = total;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> limit[i];
cout << search(1, 0) << endl;
return 0;
}
Level 2: Standard DP
#include <bits/stdc++.h>
using namespace std;
const int N = 109, MOD = 1000007;
int ways[N][N], a[N], n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
ways[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
if (j - 1 < a[i])
ways[i][j] = (ways[i-1][j] + ways[i][j-1]) % MOD;
else
ways[i][j] = (ways[i-1][j] + ways[i][j-1] - ways[i-1][j-1-a[i]] + MOD) % MOD;
}
}
cout << ways[n][m] << endl;
return 0;
}
Level 3: Prefix Sum Optimization
#include <bits/stdc++.h>
using namespace std;
const int MAX = 105, MOD = 1000007;
int dpCurrent[MAX], prefix[MAX], cap[MAX], n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> cap[i];
dpCurrent[0] = 1;
for (int j = 0; j <= m; ++j) prefix[j] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= 1; --j) {
int left = j - min(cap[i], j) - 1;
if (left < 0)
dpCurrent[j] = (dpCurrent[j] + prefix[j-1]) % MOD;
else
dpCurrent[j] = (dpCurrent[j] + prefix[j-1] - prefix[left] + MOD) % MOD;
}
for (int j = 1; j <= m; ++j)
prefix[j] = (prefix[j-1] + dpCurrent[j]) % MOD;
}
cout << dpCurrent[m] << endl;
return 0;
}
Level 4: Generating Function Insight
By defining G_i(x) = 1 + x + x^2 + ... + x^{a[i]}, the answer is the coefficient of x^m in the product of all G_i(x). Instead of full polynomial multiplication, observe that G_i(x) = (1 - x^{a[i]+1}) / (1 - x). The product can be computed efficiently using integer partitions or optimized NTT, though that is beyond a basic implementation.
Uneven Selection Problem
Given n actors with beauty values y[i], select exactly m while preserving original order. Minimize the sum of absolute differences betwean adjacent selected actors.
Proper state definition is the core difficulty.
const int INF = 1e9;
for (int i = 1; i <= n; ++i) dp[i][1] = 0;
for (int chosen = 2; chosen <= m; ++chosen)
for (int endIdx = chosen; endIdx <= n; ++endIdx) {
dp[endIdx][chosen] = INF;
for (int prev = chosen - 1; prev < endIdx; ++prev)
dp[endIdx][chosen] = min(dp[endIdx][chosen],
dp[prev][chosen - 1] + abs(y[endIdx] - y[prev]));
}
int answer = INF;
for (int i = m; i <= n; ++i)
answer = min(answer, dp[i][m]);
cout << answer << endl;
Maximizing Product with Inserted Multiplications
Insert k multiplication operators into an n-digit number to maximize the product of the resulting segments.
Define dp[i][j]: maximum product achievable from the first i digits using j multiplications.
#include <iostream>
#include <string>
using namespace std;
long long dp[45][60], n, k;
int digits[45];
long long segmentValue(int l, int r) {
long long val = 0;
for (int i = l; i <= r; ++i)
val = val * 10 + digits[i];
return val;
}
int main() {
string numStr;
cin >> n >> k >> numStr;
for (int i = 1; i <= n; ++i)
digits[i] = numStr[i - 1] - '0';
for (int i = 1; i <= n; ++i)
dp[i][0] = segmentValue(1, i);
for (int i = 2; i <= n; ++i)
for (int mul = 1; mul <= min(i - 1, (int)k); ++mul)
for (int cut = mul; cut < i; ++cut)
dp[i][mul] = max(dp[i][mul], dp[cut][mul - 1] * segmentValue(cut + 1, i));
cout << dp[n][k] << endl;
return 0;
}
Noodle Cutting: Expectation with Calculus
Cut a noodle of length x. If the remaining part is less than or equal to b, stop. Otherwise, you eat a portion and continue with the leftover. Find the expected number of cuts when starting with length a.
For x < d, f(x) = 0. For larger x, the expected value formula yields f(x) = 1 + ln(x/d) when x > d. Derivation uses differential elements and integration.
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
double initial, threshold;
cin >> initial >> threshold;
if (initial <= threshold)
cout << "0.000000" << endl;
else
cout << fixed << setprecision(6) << 1.0 + log(initial / threshold) << endl;
}
return 0;
}