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);
            }
        }