# 题目：2023B-代表团坐车
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：背包DP
# 代码看不懂的地方，请直接在群上提问


nums = list(map(int, input().split(",")))
max_num = int(input())


# 构建一维的dp数组
# dp[i]表示车载人数为i时，一共有多少种乘坐方案
dp = [0] * (max_num + 1)
# 初始化dp[0]为1，表示车为空的时候，只有一种情况
dp[0] = 1


# 遍历每一个代表团的人数num
for num in nums:
    # 逆序遍历范围 [0, max_num - num] 对应的车载人数为 pre_num 时乘坐方案数目 dp[pre_num]
    # 考虑加上当前人数num的总人数 pre_num + num 所对应的方案数 dp[pre_num + num]
    # 应该递增 dp[pre_num] 种方案数
    for pre_num in range(max_num - num, -1, -1):
        dp[num + pre_num] += dp[pre_num]
        
    # 注意1：之所以遍历的右边界选择 max_num - num，
    # 是因为如果 pre_num > max_num - num，则存在 pre_num + num > max_num 会超出最大数目

    # 注意2：之所以选择【逆序遍历】而非顺序遍历，是因为要避免以下情况：
    # max_num = 10，num = 4
    # 如果是顺序遍历pre_num（范围是0到6），会先计算dp[4]再计算dp[8]，
    # 这样dp[8] += dp[4]的计算结果不正确，因为此时dp[4]已经考虑了把num加入车载的情况

    # 如果是逆序遍历pre_num（范围是6到0），会先计算dp[8]再计算dp[4]，
    # 这样dp[8] += dp[4]的计算结果正确，因为此时dp[4]尚未考虑把num加入车载的情况

# 输出dp[-1]或者dp[max_num]
# 表示车载人数为max_num时，一共有多少种乘坐方案，即为答案
print(dp[-1])

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] numsStr = scanner.nextLine().split(",");
        int maxNum = scanner.nextInt();

        int[] nums = new int[numsStr.length];
        for (int i = 0; i < numsStr.length; i++) {
            nums[i] = Integer.parseInt(numsStr[i]);
        }

        int[] dp = new int[maxNum + 1];
        dp[0] = 1;

        for (int num : nums) {
            for (int preNum = maxNum - num; preNum >= 0; preNum--) {
                dp[num + preNum] += dp[preNum];
            }
        }

        System.out.println(dp[maxNum]);
    }
}

C++

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);

    vector<int> nums;
    int num;
    while (ss >> num) {
        nums.push_back(num);
        if (ss.peek() == ',') ss.ignore();
    }

    int maxNum;
    cin >> maxNum;

    vector<int> dp(maxNum + 1, 0);
    dp[0] = 1;

    for (int i = 0; i < nums.size(); i++) {
        int num = nums[i];
        for (int preNum = maxNum - num; preNum >= 0; preNum--) {
            dp[num + preNum] += dp[preNum];
        }
    }

    cout << dp[maxNum] << endl;

    return 0;
}

时空复杂度

时间复杂度：O(``max_num*N``)。N为代表团数量，需要遍历每一个代表团的人数num，然后考虑max_num-num种前置车载人数的方案数。

空间复杂度：O(``max_num``)。dp数组所占空间。