C++ 动态规划面试题
1. 什么是动态规划？基本思想是什么？
答案：
- 定义将复杂问题分解为子问题保存子问题的解，避免重复计算自底向上或自顶向下求解
- 基本要素最优子结构：问题的最优解包含子问题的最优解重叠子问题：子问题会被多次求解状态转移方程：描述状态之间的关系
- 与分治的区别分治：子问题独立，不重叠动态规划：子问题重叠，需要记忆化
- 两种实现方式自顶向下（记忆化搜索）：递归+缓存自底向上（迭代）：填表法
2. 斐波那契数列的动态规划解法？
答案：
- 问题F(0) = 0, F(1) = 1F(n) = F(n-1) + F(n-2)
- 递归（低效）
int fib(int n) {
if (n <= 1) return n;
return fib(n-1) + fib(n-2); // O(2^n)
}
- 记忆化搜索
int fib(int n, vector<int>& memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);
return memo[n];
}
- 动态规划
int fib(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
- 空间优化
int fib(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
3. 0-1背包问题如何解决？
答案：
- 问题描述n个物品，每个有重量w[i]和价值v[i]背包容量W每个物品只能选一次求最大价值
- 状态定义dpi：前i个物品，容量j的最大价值
- 状态转移
dp[i][j] = max(
dp[i-1][j], // 不选第i个物品
dp[i-1][j-w[i]] + v[i] // 选第i个物品
)
- 实现
int knapsack(vector<int>& w, vector<int>& v, int W) {
int n = w.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
dp[i][j] = dp[i-1][j];
if (j >= w[i-1]) {
dp[i][j] = max(dp[i][j],
dp[i-1][j-w[i-1]] + v[i-1]);
}
}
}
return dp[n][W];
}
- 空间优化（滚动数组）
int knapsack(vector<int>& w, vector<int>& v, int W) {
vector<int> dp(W + 1, 0);
for (int i = 0; i < w.size(); i++) {
for (int j = W; j >= w[i]; j--) { // 逆序
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[W];
}
4. 最长公共子序列（LCS）问题？
答案：
- 问题描述给定两个序列，找最长公共子序列子序列不要求连续
- 状态定义dpi：s1前i个字符和s2前j个字符的LCS长度
- 状态转移
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 实现
int lcs(string s1, string s2) {
int m = s1.size(), n = s2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
5. 最长递增子序列（LIS）问题？
答案：
- 问题描述找数组中最长的严格递增子序列
- 动态规划O(n²)dp[i]：以arr[i]结尾的LIS长度
int lis(vector<int>& arr) {
int n = arr.size();
vector<int> dp(n, 1);
int maxLen = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxLen = max(maxLen, dp[i]);
}
return maxLen;
}
- 二分优化O(n log n)维护一个递增数组tailtail[i]：长度为i+1的LIS的最小结尾元素
int lis(vector<int>& arr) {
vector<int> tail;
for (int num : arr) {
auto it = lower_bound(tail.begin(), tail.end(), num);
if (it == tail.end()) {
tail.push_back(num);
} else {
*it = num;
}
}
return tail.size();
}
6. 编辑距离问题？
答案：
- 问题描述将字符串s1转换为s2的最少操作次数操作：插入、删除、替换
- 状态定义dpi：s1前i个字符转换为s2前j个字符的最少操作
- 状态转移
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1]
else
dp[i][j] = 1 + min(
dp[i-1][j], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1] // 替换
)
- 实现
int editDistance(string s1, string s2) {
int m = s1.size(), n = s2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + min({dp[i-1][j],
dp[i][j-1],
dp[i-1][j-1]});
}
}
}
return dp[m][n];
}
7. 股票买卖问题？
答案：
- 只能交易一次找最大利润：max(prices[i] - minPrice)
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX, maxProfit = 0;
for (int price : prices) {
minPrice = min(minPrice, price);
maxProfit = max(maxProfit, price - minPrice);
}
return maxProfit;
}
- 可以交易多次累加所有上涨区间
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < prices.size(); i++) {
if (prices[i] > prices[i-1]) {
profit += prices[i] - prices[i-1];
}
}
return profit;
}
- 最多交易k次dpi：第i天完成j次交易的最大利润状态转移较复杂，需要维护买入和卖出状态
8. 打家劫舍问题？
答案：
- 问题描述不能抢劫相邻的房子求最大金额
- 状态定义dp[i]：前i个房子的最大金额
- 状态转移
dp[i] = max(
dp[i-1], // 不抢第i个
dp[i-2] + nums[i] // 抢第i个
)
- 实现
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
vector<int> dp(n);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i]);
}
return dp[n-1];
}
- 空间优化
int rob(vector<int>& nums) {
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
9. 区间DP问题？
答案：
- 特点状态定义在区间上dpi表示区间[i,j]的答案通常按区间长度递推
- 矩阵链乘法问题：n个矩阵相乘，求最少乘法次数dpi：矩阵i到j的最少乘法次数
int matrixChainOrder(vector<int>& dims) {
int n = dims.size() - 1;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; len++) {
for (int i = 0; i < n - len + 1; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j] +
dims[i] * dims[k+1] * dims[j+1];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}
10. 状态压缩DP？
答案：
- 定义用整数的二进制位表示状态适用于状态数较少的问题通常n <= 20
- 旅行商问题（TSP）访问所有城市一次，回到起点，最短路径dpmask：访问过mask中的城市，当前在i的最短路径
int tsp(vector<vector<int>>& dist) {
int n = dist.size();
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
dp[1][0] = 0;
for (int mask = 1; mask < (1 << n); mask++) {
for (int i = 0; i < n; i++) {
if (!(mask & (1 << i))) continue;
for (int j = 0; j < n; j++) {
if (mask & (1 << j)) continue;
int newMask = mask | (1 << j);
dp[newMask][j] = min(dp[newMask][j],
dp[mask][i] + dist[i][j]);
}
}
}
int ans = INT_MAX;
for (int i = 1; i < n; i++) {
ans = min(ans, dp[(1<<n)-1][i] + dist[i][0]);
}
return ans;
}
- 位运算技巧设置第i位：mask | (1 << i)清除第i位：mask & ~(1 << i)检查第i位：mask & (1 << i)遍历子集：for (int sub = mask; sub; sub = (sub-1) & mask)
C++面试总结 文章被收录于专栏
本专栏系统梳理C++面试高频考点，从基础语法、内存管理、STL与设计模式，到操作系统与项目实战，结合真实面试题深度解析，帮助开发者高效查漏补缺，提升技术理解与面试通过率，打造扎实的C++工程能力。
查看19道真题和解析
