2维完全背包 无空间优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 30, M = 10010;
typedef long long LL;
LL dp[M][M];
int n, m;


int main(){
    cin >> n >> m;
    dp[0][0] = 1;

    for (int i = 1; i <= n; i ++ ){
        int v;
        cin >> v;
        for (int j = 0; j <= m; j ++ ){
            // 第i种钱取0个
            dp[i][j] = dp[i - 1][j];
            // 第i中钱取1个或以上
            if (j >= v){
                dp[i][j] += dp[i][j - v];
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

空间优化

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 30, M = 10010;
typedef long long LL;
LL dp[M];
int n, m;


int main(){
    cin >> n >> m;
    dp[0] = 1;

    for (int i = 1; i <= n; i ++ ){
        int v;
        cin >> v;
        for (int j = v; j <= m; j ++ ){
            // j从小到大 ; j - v < j && j - v 从小到大 所以均是第i层循环计算出的
            dp[j] = dp[j] + dp[j - v];
        }
    }
    cout << dp[m] << endl;
    return 0;
}