思路

前排爆int警告,经典的完全背包问题求方案数, 优化为一维DP后, 顺向更新f[i], 初始条件为f[0]=1, 转移方程为f[j]=f[j]+f[j-v]

c++ 货币系统: 完全背包问题

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=3005;
int n, m;
LL f[N];

int main(){
    // 完全背包问题
    memset(f, 0x00, sizeof f);
    cin>>n>>m;
    int v;
    f[0]=1;
    for(int i=0; i<n; ++i){
        cin>>v;
        for(int j=v; j<=m; ++j)
            f[j]+=f[j-v];
    }
    cout<<f[m]<<endl;
    return 0;
}

python

class Solution:
    def main(self, n:int, m:int):
        f=[0 for _ in range(m+1)]
        f[0]=1
        for _ in range(n):
            v=int(input())
            for j in range(v, m+1):
                f[j]+=f[j-v]
        print(f[m])



if __name__ == '__main__':
    n, m=map(int, input().split())
    sol=Solution()
    sol.main(n, m)