9种背包问题中文翻译：

1. 0-1背包 - 经典版本，每个物品最多只能取一次
2. 完全背包 - 每个物品可以取无限次
3. 多重背包 - 每个物品有特定的数量限制
4. 混合背包 - 0-1背包、完全背包和多重背包的组合
5. 二维背包 - 物品同时有重量和体积两个约束
6. 分组背包 - 物品分组，每组最多只能选一个
7. 有依赖的背包 - 物品有依赖关系（必须先选父物品才能选子物品）
8. 有限背包 - 使用二进制优化的版本
9. 多维背包 - 多个约束维度

常见LeetCode子串问题中文翻译及题号：

1. 最长公共子序列 (LCS) - LeetCode 1143 - 经典DP问题
2. 最长递增子序列 (LIS) - LeetCode 300 - 包含O(n²)和O(n log n)两种版本
3. 最长回文子串 - LeetCode 5 - 找到字符串中最长的回文
4. 编辑距离 - LeetCode 72 - 将一个字符串转换为另一个字符串的最少操作数
5. 最大子数组和 - LeetCode 53 - Kadane算法求最大和子数组
6. 零钱兑换 - LeetCode 322 - 凑成目标金额所需的最少硬币数
7. 打家劫舍 - LeetCode 198 - 在不能偷相邻房屋的情况下偷到最多钱
8. 单词拆分 - LeetCode 139 - 检查字符串是否可以被拆分为字典中的单词

相关的背包问题LeetCode题号：

背包变种题目：
- 零钱兑换 - LeetCode 322 (完全背包)
- 零钱兑换 II - LeetCode 518 (完全背包求方案数)
- 分割等和子集 - LeetCode 416 (0-1背包)
- 目标和 - LeetCode 494 (0-1背包变种)
- 一和零 - LeetCode 474 (二维背包)
- 完全平方数 - LeetCode 279 (完全背包)
- 组合总和 IV - LeetCode 377 (完全背包)
- 打家劫舍 - LeetCode 198 (线性DP)
- 打家劫舍 II - LeetCode 213 (环形DP)
- 打家劫舍 III - LeetCode 337 (树形DP)

这些题目涵盖了背包问题的各种变形，是动态规划学习的经典题目！

1. Longest Common Subsequence (LCS) - Classic DP problem 1143
2. Longest Increasing Subsequence (LIS) - Both O(n²) and O(n log n) versions
3. Longest Palindromic Substring - Find the longest palindrome in a string
4. Edit Distance - Minimum operations to transform one string to another
5. Maximum Subarray - Kadane’s algorithm for maximum sum subarray
6. Coin Change - Minimum coins needed to make a target amount
7. House Robber - Maximum money without robbing adjacent houses
8. Word Break - Check if string can be segmented into dictionary words

1143 LCS

const int N = 1010;
class Solution {
public:
    int dp[N][N];
    int longestCommonSubsequence(string text1, string text2) {
        //dp[0][0] = 0;
        int n = text1.size(), m = text2.size();
        for (int i = 0; i <=n;i++) dp[i][0] = 0;
        for (int j = 0; j <=m;j++) dp[0][j] = 0; //也可以偷懒整个矩阵全部都初始化为0。
        for (int i = 1; i <= n;i++){
            for (int j = 1 ; j <= m;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[n][m];
    }
};

300 LIS

const int N = 2505;
class Solution {
public:
    int dp[N];
    int lengthOfLIS(vector<int>& nums) {
        int res = 1;
        for (int i = 0;i<= nums.size();i++) dp[i] = 1;
        for (int i = 1;i< nums.size();i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
            if (dp[i] > res) res = dp[i];
        }
        return res;
    }
};

背包9讲(男人几题)

Excellent! The program runs perfectly. Here’s what I’ve implemented for you:

9 Types of Knapsack Problems:

1. 0-1 Knapsack - Classic version where each item can be taken at most once
2. Unbounded Knapsack - Items can be taken multiple times
3. Multiple Knapsack - Each item has a specific count limit
4. Mixed Knapsack - Combination of 0-1, unbounded, and multiple constraints
5. Two-Dimensional Knapsack - Items have both weight and volume constraints
6. Grouped Knapsack - Items are grouped, can select at most one from each group
7. Dependent Knapsack - Items have dependencies (must take parent before child)
8. Bounded Knapsack - Optimized version using binary optimization
9. Multi-Dimensional Knapsack - Multiple constraint dimensions