动态规划4 数字组合

描述有n个正整数，找出其中和为t(t也是正整数)的可能的组合方式。如： n=5,5个数分别为1,2,3,4,5，t=5； 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。输入输入的第一行是两个正整数n和t，用空格隔开，其中1<=n<=20,表示正整数的个数，t为要求的和(1<=t<=1000) 接下来的一行是n个正整数，用空格隔开。输出和为t的不同的组合方式的数目。样例输入 5 5 1 2 3 4 5

样例输出

3

#include<iostream> using namespace std; int a[1001]; int main() { int n,t,b; cin>>n>>t; a[0]=1; for(int i=1;i<=n;i++) { cin>>b; for(int j=t;j>=b;j--) a[j]+=a[j-b]; } cout<<a[t]; return 0; }

每输入一个b，例如b=2；

那么5=2+3，4=2+2，3=1+2，2=2+0；

如果按照1，2，3，4，5输入

那么当输入1是

a[1]=1,a[2]=0,a[3]=0,a[4]=0,a[5]=0;

2时

a[1]=1,a[2]=1,a[3]=1,a[4]=0,a[5]=0;

3时

a[1]=1,a[2]=1,a[3]=2,a[4]=1,a[5]=1;

4时

a[1]=1,a[2]=1,a[3]=2,a[4]=2,a[5]=2;

5时

a[1]=1,a[2]=1,a[3]=2,a[4]=2,a[5]=3;

对于输入的每一个数

都要查看对于a[j](b<=j<t)有没有可能组成所以

a[j]的值取决于a[j-b]的值

即可推出a【j】+=a【j-b】的转移公式