【算法】给定一个有n个正整数的数组A和一个整数sum，求选择数组A中部分数字和为sum的方案数（C++源码）
一、问题描述
给定一个有n个正整数的数组a和一个整数sum，求选择数组a中部分数字和为sum的方案数。若两种选取方案有一个数字的下标不一样，则认为是不同的方案。
二、输入描述
输入为两行，第1行为两个正整数n和sum，第2行为n个正整数，以空格隔开。
三、输出描述
输出所求的方案数。
四、样例
5 15
5 5 10 2 3
五、输出
4
六、步骤描述
动态规划问题，构建一个dp二维数组，将第一行第一列全部置零，再将dp[0][0]=1;上下传值，并判断若满足给定的约束条件，则累加。最后输出右下角元素。
七、运行结果截图
八、源代码（C++）
#include <iostream>
using namespace std;
int main()
{
int dp[100][100];
int n;
int a[100];
int sum;
cin>>n>>sum;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=1;i<=sum;i++)
{
dp[0][i]=0;
}
for(int i=1;i<=n;i++)
{
dp[i][0]=0;
}
dp[0][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
dp[i][j]=dp[i-1][j];
if(j>=a[i-1])
{
dp[i][j]=dp[i][j]+dp[i-1][j-a[i-1]];
}
}
}
cout<<dp[n][sum]<<endl;
return 0;
}