动态规划经典问题解析与优化策略
最长递增子序列（LIS）
给定一个长度为 $ N $ 的整数序列，求其严格单调递增的子序列的最大长度。
- 基础解法：状态 $ dp[i] $ 表示以第 $ i $ 个元素结尾的最长递增子序列长度。枚举所有 $ j < i $ 且 $ a[j] < a[i] $ 的位置进行转移，时间复杂度 $ O(N^2) $。
for (int i = 1; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j)
if (a[j] < a[i])
dp[i] = max(dp[i], dp[j] + 1);
}
cout << *max_element(dp + 1, dp + n + 1) << '\n';- 优化解法：利用离散化和树状数组维护前缀最大值。对每个 $ a[i] $，查询值域小于 $ a[i] $ 的最大 $ dp $ 值，并更新当前位置。总复杂度降为 $ O(N \log N) $。
auto vals = a;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
function<int(int)> get_id = [&](int x) {
return lower_bound(vals.begin(), vals.end(), x) - vals.begin() + 1;
};
for (int i = 1; i <= n; ++i) {
int id = get_id(a[i]);
dp[i] = bit.query(id - 1) + 1;
bit.update(id, dp[i]);
}括号匹配问题（POJ2955）
给定仅包含 ()[] 的字符串，求最多能匹配多少对合法括号。
定义 $ f[l][r] $ 为区间 $ [l,r] $ 内的最大匹配数。
- 若 $ s[l] $ 与 $ s[r] $ 可配对，则可由 $ f[l+1][r-1] + 2 $ 转移而来。
- 枚举分割点 $ k $，尝试合并左右两段：$ f[l][r] = \max(f[l][k] + f[k+1][r]) $。
for (int len = 2; len <= n; ++len)
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
if ((s[l]=='(' && s[r]==')') || (s[l]=='[' && s[r]==']'))
f[l][r] = max(f[l][r], f[l+1][r-1] + 2);
for (int k = l; k < r; ++k)
f[l][r] = max(f[l][r], f[l][k] + f[k+1][r]);
}整数划分方案数
求将正整数 $ N $ 划分为若干正整数之和的不同方式数量（顺序不同视为相同）。
转化为完全背包问题：物品为数字 $ 1 $ 到 $ N $，每种可用无限次，容量为 $ N $，求填满背包的方法总数。
vector<long long> dp(n + 1);
dp[0] = 1;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
dp[j] += dp[j - i];
cout << dp[n] << '\n';最长回文子串
给定字符串 $ str $，找出其中最长回文子串的长度。
使用区间 DP：设 $ f[i][j] $ 表示子串 $ s[i..j] $ 是否为回文串。
- 初始化单字符和双字符情况。
- 状态转移：若 $ s[i] == s[j] $ 且中间部分是回文，则整体也是回文。
vector<vector<bool>> f(n, vector<bool>(n, false));
int ans = 1;
for (int i = 0; i < n; ++i) f[i][i] = true;
for (int i = 0; i < n - 1; ++i)
if (s[i] == s[i+1]) {
f[i][i+1] = true;
ans = 2;
}
for (int len = 3; len <= n; ++len)
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1;
if (s[i] == s[j] && f[i+1][j-1]) {
f[i][j] = true;
ans = len;
}
}田忌赛马（POJ2287）
两人各有 $ N $ 匹马，按速度排序后轮流出马比拼。赢一场得一分，输一场扣一分，平局不得分。齐王按从快到慢出马，求田忌最优策略下的最高得分。
关键观察：每次决策时，当前最弱或最强的马是最优选择之一。采用区间 DP 求解。
- 状态 $ dp[l][r] $：表示剩余马匹在原数组中位于区间 $ [l,r] $ 时能获得的最大收益。
- 转移时考虑用当前最弱或最强的马去应对对手已出场的第 $ (r-l+1) $ 匹马。
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1e9));
for (int i = 1; i <= n; ++i) {
int res = 0;
if (a[i] > b[n - (i - 1)]) res = 1;
else if (a[i] < b[n - (i - 1)]) res = -1;
dp[i][i] = res;
}
for (int len = 2; len <= n; ++len)
for (int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
int turn = n - len + 1; // 对手当前出的是第几快的马
int score1 = (a[l] > b[turn] ? 1 : (a[l] < b[turn] ? -1 : 0));
int score2 = (a[r] > b[turn] ? 1 : (a[r] < b[turn] ? -1 : 0));
dp[l][r] = max(dp[l+1][r] + score1, dp[l][r-1] + score2);
}
cout << dp[1][n] << '\n';花店橱窗布置（Nowcoder1005）
有 $ n $ 束花需放入 $ m $ 个花瓶（$ n \leq m $），保持花的相对顺序不变。每束花放在不同花瓶中有不同的观赏价值，求最大总价值并输出字典序最小的方案。
状态 $ dp[i][j] $：前 $ i $ 束花中最后一束放在第 $ j $ 个花瓶所能达到的最大价值。
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1e9));
vector<vector<int>> pre(n + 1, vector<int>(m + 1));
for (int j = 1; j <= m; ++j)
dp[1][j] = v[1][j];
for (int i = 2; i <= n; ++i)
for (int j = i; j <= m - (n - i); ++j)
for (int k = i - 1; k < j; ++k)
if (dp[i-1][k] + v[i][j] > dp[i][j]) {
dp[i][j] = dp[i-1][k] + v[i][j];
pre[i][j] = k;
}
int pos = max_element(dp[n].begin() + n, dp[n].end()) - dp[n].begin();
vector<int> path;
int cur = pos;
for (int i = n; i >= 1; --i) {
path.push_back(cur);
cur = pre[i][cur];
}
reverse(path.begin(), path.end());
for (int x : path) cout << x << ' ';
cout << '\n';邮票面值设计（NOIP1999）
最多贴 $ N $ 张邮票，现有 $ K $ 种不同面值，要求设计面值使得从 1 开始连续可达的邮资范围最大。
搜索 + 动态验证：
- DFS 枚举每一种可能的面值组合。
- 对于每个组合，用完全背包判断能够连续覆盖的最大值。
- 剪枝：下一个面值的上限为当前最大可达值加一。
int check(vector<int>& stamps) {
int mx = stamps.back() * n;
vector<int> dp(mx + 1, 1e9);
dp[0] = 0;
for (int x : stamps)
for (int j = x; j <= mx; ++j)
if (dp[j - x] < n)
dp[j] = min(dp[j], dp[j - x] + 1);
for (int i = 1; i <= mx; ++i)
if (dp[i] == 1e9) return i - 1;
return mx;
}
void dfs(int idx, int last, int max_reach, vector<int>& cur) {
if (idx == k) {
if (max_reach > best) {
best = max_reach;
ans = cur;
}
return;
}
for (int nxt = last + 1; nxt <= max_reach + 1; ++nxt) {
cur.push_back(nxt);
int reach = check(cur);
if (reach > max_reach)
dfs(idx + 1, nxt, reach, cur);
cur.pop_back();
}
}环形传球问题
$ N $ 个人围成一圈，从第 1 人开始传 $ M $ 次球。每次可顺时针或逆时针传 $ a_i $ 步。问是否存在一种方式使球最终回到起点。
状态 $ dp[i][j] $：表示经过前 $ i $ 次传递后是否可能位于第 $ j $ 个人（编号 $ 0 $ 到 $ N-1 $）手中。
int n, m; cin >> n >> m;
vector<int> a(m);
for (int i = 0; i < m; ++i) cin >> a[i];
vector<vector<bool>> dp(m + 1, vector<bool>(n, false));
dp[0][0] = true;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j) if (dp[i][j]) {
int cw = (j + a[i]) % n;
int ccw = (j - a[i] + n) % n;
dp[i+1][cw] = true;
dp[i+1][ccw] = true;
}
cout << (dp[m][0] ? "YES" : "NO") << '\n';桥梁建设最小成本（Codeforces E题）
在一个 $ n \times m $ 网格河流上建造 $ k $ 座连续行上的桥。每行独立建桥，首尾列必须安装支撑，相邻支撑间距不超过 $ d $。每个格子建支撑的成本为 $ a[i][j]+1 $，求最小总成本。
逐行计算最小建桥成本，再滑动窗口求连续 $ k $ 行的最小和。
对每一行使用单调队列优化的 DP：
- 状态 $ dp[j] $：到达第 $ j $ 列且在此设置支撑的最小代价。
- 转移：$ dp[j] = \min_{|j-k|\leq d+1} (dp[k]) + cost[j] $。
deque<pair<long long, int>> dq;
vector<long long> row_cost;
for (int r = 0; r < n; ++r) {
vector<long long> dp(m, 1e18);
dq.clear();
dp[0] = g[r][0];
dq.push_back({dp[0], 0});
for (int j = 1; j < m; ++j) {
while (!dq.empty() && j - dq.front().second > d + 1)
dq.pop_front();
dp[j] = dq.front().first + g[r][j];
while (!dq.empty() && dp[j] <= dq.back().first)
dq.pop_back();
dq.push_back({dp[j], j});
}
row_cost.push_back(dp[m-1]);
}
// 计算连续 k 行的最小总成本
long long total = 0;
for (int i = 0; i < k; ++i) total += row_cost[i];
long long ans = total;
for (int i = k; i < n; ++i) {
total += row_cost[i] - row_cost[i - k];
ans = min(ans, total);
}
cout << ans << '\n';