题解 | 数字和为sum的方法数

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

int main() {
    int n, sum;
    cin >> n >> sum;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i];
    
    // 动态规划
    // --- 状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i - 1][j - arr[i]]
    // --- i是前i个数，j是sum（j - arr[i]即是指，加上当前数）
    vector<vector<long long>> dp(n, vector<long long>(sum + 1, 0));

    dp[0][0] = 1;   // 什么都不选，和为0的组合有 1 种
    if (arr[0] <= sum)
        dp[0][arr[0]] = 1; // 选择第一个数，和为 arr[0] 的组合有 1 种
    
    for (int i = 1; i < n; ++i) {
        for (long long j = 0; j <= sum; ++j) {
            dp[i][j] = dp[i - 1][j];
            if (j >= arr[i])
                dp[i][j] += dp[i - 1][j - arr[i]];
        }
    }
    cout << dp[n - 1][sum] << endl;
    return 0;
}