C++ 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2017-09-07

#include <iostream>
#include<algorithm>
#include <vector>
#include<unordered_map>  
#include <string>
using namespace std;


int main()
{
	long long n, sum;
	cin >> n >> sum;
	vector<long long> a(n, 0);
	for (int i = 0; i < n; i++)
		cin >> a[i];
	//sort(a.begin(),  a.end());
	vector <long long> dp(sum + 1, 0);
	for (int i = 0; i < n; i++)
	{
		if (a[i] > sum)
			continue;
		for (long long j = sum; j > 0; j--)
			if (dp[j] > 0 && j + a[i] <= sum)
				dp[j + a[i]] += dp[j];
		dp[a[i]]++;
	}
	cout << dp[sum] << endl;
	return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-23

#include<iostream>
#include<vector>

using namespace std;

int ans;
void helper(const vector<int> & nums,int i, int sum)
    {
    	if(i == nums.size()) return ;
    
    	if(sum < 0) return;
    	if(sum == 0)
            {
            ans ++;
            return ;
        }
    helper(nums,i+1,sum);
    helper(nums,i+1,sum - nums[i]);
}

void solutions()
    {
    int n , sum;
    cin >> n >> sum;
    vector<int>nums;
   	ans = 0;
    for(int i = 0; i < n;i ++)
        {
        int v;
        cin >> v;
        nums.push_back(v);
    }
    
    long long  dp[sum+1];
    
    for(int i = 0; i < n+1;i++)
        {
        for(int j = sum; j >=0; j--)
            {
            if(j==0)
                {
                dp[j] = 1;
            }
            else if(i ==0) dp[j] = 0;
            else
                if(j >= nums[i-1])
                {
                    dp[j] = dp[j] + dp[j-nums[i-1]];
                }
            else
                dp[j] = dp[j];
        }
    }
    
    cout << dp[sum] << endl;
}
int main()
    {
    solutions();
    return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-23

#include <iostream>
using namespace std;

long long dp[1000];
int main()
{
    int n,sum;
    cin>>n>>sum;
 
    int p[1000];
    for(int i = 1 ; i <= n ; i++)
        cin>>p[i];
//初始化dp,用前i个组成和为0的方案，只有1种，就是什么都不取，和为0；
    dp[0] = 1;
//用0个元素不能组成1~sum
    for (int j = 1 ; j < sum ;j++)
    {
        dp[j] = 0;
    }
 
    for (int i = 1 ; i <= n ;i++)
    {
        for (int j = sum ; j>0 ;j--)
        {
            if(j-p[i] >= 0) 
                dp[j] = dp[j]+dp[j-p[i]];
        }
    }
    cout<<dp[sum]<<endl;
    return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-10

#include <iostream>
#include <algorithm>
using namespace std;
//注意：最终结果int类型存不下，需要64位数据
//注意：dp不能放在main里，栈存不下。需要存在全局数据区
long long dp[1000];
int main()
{
    int n,sum;
    cin>>n>>sum;
 
    int p[1000];
    for(int i = 1 ; i <= n ; i++)
        cin>>p[i];
    //用0个元素不能组成1~sum
    for (int j = 1 ; j < sum ;j++)
    {
        dp[j] = 0;
    }
 	dp[0] = 1;
    for (int i = 1 ; i <= n ;i++)
    {
        for (int j = sum ; j>=1 ;--j)
        {
            if(p[i]<=j) dp[j] = dp[j]+dp[j-p[i]];
        }
    }
    cout<<dp[sum]<<endl;
    return 0;
}

C++ 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2017-09-10

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<memory.h>
using namespace std;
#define MAX 1005

/*
int main()
{
    int n,m;
    int arr[MAX];
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>arr[i];
    long long dp[MAX][MAX];
    memset(dp,0,sizeof(dp));

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = 1;
        for(int j = 0; j <= m; j++)
        {
            if(j < arr[i])
            {
                dp[i][j] = dp[i-1][j];
            }
            else
            {
                dp[i][j] = dp[i-1][j] + dp[i-1][j-arr[i]];
            }
        }
    }
//    for(int i = 0; i <= n; i++)
//    {
//        for(int j = 0; j <= m; j++)
//        {
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    cout<<dp[n][m]<<endl;

    return 0;
}

*/
int main()
{
    int n,m;
    int arr[MAX];
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>arr[i];
    long long dp[MAX];
    memset(dp,0,sizeof(dp));

    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >=  arr[i]; j--)
        {
           dp[j] = dp[j] + dp[j-arr[i]];
        }
    }

    cout<<dp[m]<<endl;

    return 0;
}