如何计算篮球得分组合数 C++动态规划memset使用问题求助

代码存在的问题 #

• 动态规划遍历顺序错误：当前逻辑统计的是得分的排列数而非组合数。外层遍历目标金额、内层遍历得分面值的写法，会把1+2和2+1这类构成相同、顺序不同的情况判定为两种结果，不符合组合计数的要求。求组合数的正确遍历顺序是外层遍历得分面值，内层遍历目标金额，保证每种面值仅按顺序统计一次，避免重复计数。
• 使用非标准语法：int dp[n+1]属于变长数组（VLA），并不是C++标准支持的语法，仅为部分编译器的扩展实现，可移植性差，建议改用vector容器实现，初始化时可直接赋值为0，不需要额外调用memset。
• 输出逻辑错误：当前代码会在循环中依次输出1到n所有金额的组合数，且没有分隔符，不会单独输出n对应的最终结果，需要把输出语句移到循环外部。
• memset在这里的使用没有逻辑错误（给int数组赋值为0时符合预期），但memset是按字节赋值，如果后续需要给数组赋非0值会出现预期外的结果，改用vector初始化的方式更稳妥。

修正后可正常运行的代码 #

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

int main() {
    int n;
    cin >> n;
    int score_type[3] = {1, 2, 3};
    vector<int> dp(n + 1, 0);
    dp[0] = 1; // 基础边界：得分为0时只有1种组合（所有得分方式都选0次）
    
    // 外层遍历得分类型
    for (int j = 0; j < 3; j++) {
        // 内层遍历金额，从当前得分面值开始避免越界
        for (int i = score_type[j]; i <= n; i++) {
            dp[i] += dp[i - score_type[j]];
        }
    }
    cout << dp[n] << endl;
    return 0;
}

输入n=5时，代码输出结果为4，符合示例要求。

内容的提问来源于stack exchange，提问作者Oliver Mendez