题解 | #数字和为sum的方法数#
数字和为sum的方法数
https://www.nowcoder.com/practice/7f24eb7266ce4b0792ce8721d6259800
#include <iostream> using namespace std; const int MAXN = 1e3+5; #define ll long long int a[MAXN],n,sum; ll dp[MAXN][MAXN]; //dp[i][j]: 前i个数组成j的方案数 int main() { cin>>n>>sum; for(int i=0;i<n;i++) cin>>a[i]; dp[0][a[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]) dp[i][j] += dp[i-1][j-a[i]];//选择第i个数 if(j==a[i]) dp[i][j] += 1;//第i个数可单独组成j } } cout<<dp[n-1][sum]<<endl; } // 64 位输出请用 printf("%lld")