c++ 二维dp 完全背包

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

const int N=1005;
int f[5][N];
int v[5]={0, 10, 20, 50, 100};
int n;

int main(){
    memset(f, 0x00, sizeof f);
    cin>>n;
    f[0][0]=1;
    for(int i=1; i<=4; ++i){
        for(int j=0; j<=n; ++j){
            f[i][j]=f[i-1][j];
            if(j>=v[i]) f[i][j]+=f[i][j-v[i]];
        }
    }
    cout<<f[4][n]<<endl;

    return 0;
}

c++ 一维优化 完全背包

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

const int N=1005;
int f[N];
int v[5]={0, 10, 20, 50, 100};
int n;

int main(){
    memset(f, 0x00, sizeof f);
    cin>>n;
    f[0]=1;
    for(int i=1; i<=4; ++i){
        for(int j=v[i]; j<=n; ++j){ // 正向枚举体积
            f[j]+=f[j-v[i]];
        }
    }
    cout<<f[n]<<endl;

    return 0;
}

python 一维

class Solution:
    def main(self, n:int):
        v=[10, 20, 50, 100]
        f=[0 for _ in range(n+1)]
        f[0]=1
        for i in v:
            for j in range(i, n+1):
                f[j]+=f[j-i]
        print(f[n])

if __name__ == '__main__':
    n=int(input())
    sol=Solution()
    sol.main(n)