int momo[100001];
int fbnq(int n){
    if(n==1)return 0;
    if(n==2)return 1;
    if(momo[n]!=0)return momo[n];
    momo[n]=fbnq(n-1)+fbnq(n-2);
    return momo[n];
}
//利用空间（momo数组存储已经计算出的结果，已经计算出结果的不用再重复算）换时间
// 时间复杂度：从优化到
// 原因：每个子问题只需计算一次
// 递归树节点数等于问题规模n
// 空间复杂度：（存储备忘录数组）
// 关键改进：
// 通过空间换时间，消除重叠子问题
// 计算过的值直接查表返回