题目链接 1001-方块与收纳盒_2021秋季算法入门班第七章习题：动态规划1 (nowcoder.com)
一道简单的线性dp的题目（入门题目）
题面分析：有一个n*1大小的盒子，你有无限个1*1和2*1的小方块，问你有几种方法可以把这个盒子填满
（注：填入的顺序不同也算不同的方法（见下面的例子））
例如：n=4
方法1：1 1 1 1
方法2：2 1 1
方法3：1 2 1
方法4：1 1 2
方法5：2 2
总共5种方法
分析：斐波那契数列（递推）
1*1只有一个方法，2*1有两种方法 （法1：1 1 法2：2）
然后可以很简单的发现，n>=3时，它要么从（n-1）*1的情况加一个1*1或者从（n-2）*1的情况加一个2*1（后面以此类推即可）
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#define INF 0x3f3f3f3f
#define int long long
#define lowbits(x) (x&(-x))
using namespace std;
typedef pair <int,int> PII;
const int N =2e5+10;
int dp[100];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++) dp[i]=0;dp[1]=1; //1*1的方法数dp[2]=2; //2*1的方法数for(int i=3;i<=n;i++){dp[i]=dp[i-2]+dp[i-1]; //n>=3时的递推}cout<<dp[n]<<endl;
}signed main(){std::ios::sync_with_stdio(false), cin.tie(0),cout.tie(0); //输入输出加速int t;cin>>t;while(t--){solve();}
}
