C++算法（动态规划）

1. 斐波那契数列（Fibonacci Sequence）

问题描述：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

// 方法1：递归（效率低，存在大量重复计算）
// 时间复杂度：O(2^n)，空间复杂度：O(n)
int fibonacci1(int n) {
    if (n <= 1) return n;
    return fibonacci1(n - 1) + fibonacci1(n - 2);
}

// 方法2：记忆化搜索
// 时间复杂度：O(n)，空间复杂度：O(n)
int fibonacci2(int n, vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacci2(n - 1, memo) + fibonacci2(n - 2, memo);
    return memo[n];
}

// 方法3：动态规划（自底向上）
// 时间复杂度：O(n)，空间复杂度：O(n)
int fibonacci3(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];
}

// 方法4：空间优化版本
// 时间复杂度：O(n)，空间复杂度：O(1)
int fibonacci4(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;
}

// 方法5：矩阵快速幂
// 时间复杂度：O(log n)，空间复杂度：O(1)
int fibonacci5(int n) {
    if (n <= 1) return n;
    // 使用矩阵 [[1,1],[1,0]]^n 计算
    // 实现略
}

2. 0/1 背包问题（0/1 Knapsack）

问题描述：给定 n 个物品，每个物品有重量和价值，背包容量为 W，求最大价值

// 方法1：二维 DP
// 时间复杂度：O(n*W)，空间复杂度：O(n*W)
int knapsack01_2D(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    // dp[i][w] 表示前 i 个物品，容量为 w 时的最大价值
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            // 不选第 i 个物品
            dp[i][w] = dp[i - 1][w];
            
            // 选第 i 个物品（如果能放下）
            if (w >= weights[i - 1]) {
                dp[i][w] = max(dp[i][w], 
                              dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    return dp[n][W];
}

// 方法2：一维 DP（空间优化）
// 时间复杂度：O(n*W)，空间复杂度：O(W)
int knapsack01_1D(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);
    
    for (int i = 0; i < n; i++) {
        // 必须从后向前遍历，避免重复使用物品
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}

// 回溯找出选择的物品
vector<int> knapsackWithItems(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    
    // 填充 DP 表
    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            dp[i][w] = dp[i - 1][w];
            if (w >= weights[i - 1]) {
                dp[i][w] = max(dp[i][w], 
                              dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    // 回溯找出选择的物品
    vector<int> selected;
    int w = W;
    for (int i = n; i > 0 && w > 0; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            selected.push_back(i - 1);
            w -= weights[i - 1];
        }
    }
    
    return selected;
}

// 使用示例
int main() {
    vector<int> weights = {2, 3, 4, 5};
    vector<int> values = {3, 4, 5, 6};
    int W = 8;
    cout << "最大价值: " << knapsack01_1D(weights, values, W) << endl;
}

3. 最长递增子序列（Longest Increasing Subsequence, LIS）

问题描述：找出数组中最长的严格递增子序列的长度

// 方法1：动态规划
// 时间复杂度：O(n²)，空间复杂度：O(n)
int lengthOfLIS_DP(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    int n = nums.size();
    vector<int> dp(n, 1);  // dp[i] 表示以 nums[i] 结尾的 LIS 长度
    int maxLen = 1;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLen = max(maxLen, dp[i]);
    }
    
    return maxLen;
}

// 方法2：贪心 + 二分查找（最优解）
// 时间复杂度：O(n log n)，空间复杂度：O(n)
int lengthOfLIS_Binary(vector<int>& nums) {
    if (nums.empty()) return 0;
    
    vector<int> tails;  // tails[i] 表示长度为 i+1 的 LIS 的最小尾部元素
    
    for (int num : nums) {
        // 二分查找第一个大于等于 num 的位置
        auto it = lower_bound(tails.begin(), tails.end(), num);
        
        if (it == tails.end()) {
            tails.push_back(num);  // num 比所有元素都大
        } else {
            *it = num;  // 替换为更小的元素
        }
    }
    
    return tails.size();
}

// 打印 LIS（使用 DP 方法）
vector<int> printLIS(vector<int>& nums) {
    if (nums.empty()) return {};
    
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> parent(n, -1);
    int maxLen = 1, maxIndex = 0;
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                parent[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIndex = i;
        }
    }
    
    // 回溯构建 LIS
    vector<int> lis;
    for (int i = maxIndex; i != -1; i = parent[i]) {
        lis.push_back(nums[i]);
    }
    reverse(lis.begin(), lis.end());
    
    return lis;
}

4. 最长公共子序列（Longest Common Subsequence, LCS）

问题描述：找出两个字符串的最长公共子序列长度

// 方法1：二维 DP
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[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];
}

// 方法2：空间优化（一维 DP）
// 时间复杂度：O(m*n)，空间复杂度：O(min(m,n))
int longestCommonSubsequence_Optimized(string text1, string text2) {
    if (text1.length() < text2.length()) {
        swap(text1, text2);
    }
    
    int m = text1.length(), n = text2.length();
    vector<int> dp(n + 1, 0);
    
    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
            prev = temp;
        }
    }
    
    return dp[n];
}

// 打印 LCS
string printLCS(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    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 (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // 回溯构建 LCS
    string lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (text1[i - 1] == text2[j - 1]) {
            lcs = text1[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    
    return lcs;
}

5. 最长公共子串（Longest Common Substring）

问题描述：找出两个字符串的最长公共连续子串长度

// 方法1：二维 DP
// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int longestCommonSubstring(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLen = 0;
    
    // dp[i][j] 表示以 text1[i-1] 和 text2[j-1] 结尾的最长公共子串长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLen = max(maxLen, dp[i][j]);
            }
        }
    }
    
    return maxLen;
}

// 方法2：空间优化
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int longestCommonSubstring_Optimized(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<int> dp(n + 1, 0);
    int maxLen = 0;
    
    for (int i = 1; i <= m; i++) {
        int prev = 0;
        for (int j = 1; j <= n; j++) {
            int temp = dp[j];
            if (text1[i - 1] == text2[j - 1]) {
                dp[j] = prev + 1;
                maxLen = max(maxLen, dp[j]);
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }
    
    return maxLen;
}

// 打印最长公共子串
string printLongestCommonSubstring(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int maxLen = 0, endIndex = 0;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endIndex = i - 1;
                }
            }
        }
    }
    
    return text1.substr(endIndex - maxLen + 1, maxLen);
}

6. 编辑距离（Levenshtein Distance）

问题描述：将字符串 s1 转换为 s2 所需的最少操作次数（插入、删除、替换）

// 时间复杂度：O(m*n)，空间复杂度：O(m*n)
int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // 初始化边界
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    
    // dp[i][j] 表示 word1[0..i-1] 转换为 word2[0..j-1] 的最少操作数
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];  // 不需要操作
            } else {
                dp[i][j] = min({
                    dp[i - 1][j] + 1,      // 删除
                    dp[i][j - 1] + 1,      // 插入
                    dp[i - 1][j - 1] + 1   // 替换
                });
            }
        }
    }
    
    return dp[m][n];
}

// 空间优化版本
// 时间复杂度：O(m*n)，空间复杂度：O(n)
int minDistance_Optimized(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<int> dp(n + 1);
    
    for (int j = 0; j <= n; j++) dp[j] = j;
    
    for (int i = 1; i <= m; i++) {
        int prev = dp