二维DP

#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
const int mod = 998244353;
#define md(x) (((x) % mod + mod) % mod)
#define l(s) (s << 1)
#define r(s) (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>

int n,m;

const int N=35;
const int M=3e5+5;

int a[N]; 

int f[N][M];

void work() {
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=m;j++) f[0][j]=-1;//根本就达不到要求，记为-1 

    for(int j=1;j<=m;j++)
        for(int i=1;i<=n;i++){
//          f[i][j]=-1;
//          
//          if(f[i-1][j]!=-1) f[i][j]=f[i-1][j];

            f[i][j]=f[i-1][j];//等价于上面两行,但是变成一维时用上面两行会出现问题，出现污染f[i-1][j]的情况！！！ 

            if(a[i]>=j){
                if(f[i][j]!=-1) f[i][j]=min(f[i][j],a[i]);
                else f[i][j]=a[i];
            } 

            else if(a[i]<j&&f[i-1][j-a[i]]!=-1){
                if(f[i][j]!=-1) f[i][j]=min(f[i][j],f[i-1][j-a[i]]+a[i]);
                else f[i][j]=f[i-1][j-a[i]]+a[i];
            } 


        }

    cout<<f[n][m];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int Case = 1;
    //cin >> Case;
    while (Case--){
        work(); 
        if(Case>=1)cout<<endl<<"once again:"<<endl;
    } 
    return 0;
}

一维DP

#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
const int mod = 998244353;
#define md(x) (((x) % mod + mod) % mod)
#define l(s) (s << 1)
#define r(s) (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>

int n,m;

const int N=35;
const int M=3e5+5;

int a[N]; 

int f[M];

void work() {
    cin>>n>>m;

    for(int i=1;i<=n;i++) cin>>a[i];
    for(int j=1;j<=m;j++) f[j]=-1;//根本就达不到要求，记为-1 

    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--){


//          f[j]=f[j];

            if(a[i]>=j){
                if(f[j]!=-1) f[j]=min(f[j],a[i]);
                else f[j]=a[i];
            } 

            else if(a[i]<j&&f[j-a[i]]!=-1){
                if(f[j]!=-1) f[j]=min(f[j],f[j-a[i]]+a[i]);
                else f[j]=f[j-a[i]]+a[i];
            } 


        }

    cout<<f[m];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int Case = 1;
    //cin >> Case;
    while (Case--){
        work(); 
        if(Case>=1)cout<<endl<<"once again:"<<endl;
    } 
    return 0;
}