多组背包恰好装满方案数

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

    现在有一个大小n*1的收纳盒，我们手里有无数个大小为1*1和2*1的小方块，我们需要用这些方块填满收纳盒，请问我们有多少种不同的方法填满这个收纳盒

---

分析：

  物品可以添加无数次，所以第二层循环放物体，初始化，装满0空间背包的方案数为1，即不装

---

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve()
{ll a[]={1,2};ll n;cin>>n;ll dp[n+1];memset(dp,0,sizeof dp);dp[0]=1;for(ll i=1;i<=n;i++){for(ll j=0;j<=1;j++){if(i>=a[j])dp[i]+=dp[i-a[j]];}}cout<<dp[n]<<'\n';
}int main(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t=1;cin>>t;while(t--)solve();return 0;}