$90WA$的$DFS$

$VS$

$100AC$的$DP$

$dfs$(回溯递归)做法,只是做法,不代表能$AC$

最后一个点被$hach$打败了

#include<iostream>
using namespace std;
int n,cap,sum=0;
int f[141];
int vis[114];
void dfs(int x,int s)
{
    if(s>=cap)
    {
        if(s==cap)
        {
            sum++;
        }
        return;
    }
    vis[x]=1;
    for(int i=x+1;i<=n;i++)
    {
        if(!vis[i])
        {
            dfs(i,s+f[i]);
        }
    }
    vis[x]=0;
}
int main()
{
    cin>>n>>cap;
	for(int i=1;i<=n;i++)
	{
		cin>>f[i];
	}
    dfs(0,0);
    cout<<sum;
    return 0;
}

$dp$做法,能$AC$

#include<iostream>
using namespace std;
int n,cap,sum=0;
int f[141];
int dp[11451];
int main()
{
	cin>>n>>cap;
	for(int i=1;i<=n;i++)
	{
		cin>>f[i];
	}
	dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=cap;j>=f[i];j--)
		{
			dp[j]+=dp[j-f[i]];
		}
	}
	cout<<dp[cap];
	return 0;
}

#include<bits/stdc++.h>
#define N 111
using namespace std;
int n,m,f[N][10010],a[N];
 int read()
 {
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
    return x*f;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j==a[i])f[i][j]=f[i-1][j]+1;
            if(j>a[i])f[i][j]=f[i-1][j]+f[i-1][j-a[i]];
            if(j<a[i])f[i][j]=f[i-1][j];
        }
    }
    cout<<f[n][m];
    return 0;
}

from 课件

#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,a[110],f[999999];
cin>>n>>m;
for(int i=1;i<=n;i++){
	cin>>a[i];
	
}
f[0]=1;
for(int i=1;i<=n;i++){
	for(int j=m;j>=a[i];j--){
		f[j]=f[j]+f[j-a[i]];
	}
}
cout<<f[m];
}