50分，求助大佬！！

songyuanze88 @ 2022-08-05 12:42:59

#include <bits/stdc++.h>
using namespace std;

int a[1000000];
int n;
long long cnt = 0;
void dfs(int step,int sum)
{
    if(sum > n) return;
    if(sum == n)
    {
        cnt++;
        return;
    }
    a[step] = 1;
    dfs(step+1,sum+1);
    a[step] = 2;
    dfs(step+1,sum+2);
}
int main()
{
    cin >> n;
    dfs(1,0);
    cout << cnt << endl;
    return 0;
}

by dengyujie2020 @ 2022-08-05 12:46:51

可以解释一下代码吗？这种线性DP一般用数组的，而不是记忆化搜索本蒟蒻看不懂

by MujicaSaki @ 2022-08-05 12:47:35

@songyuanze88 需要高精度

by Offending_user_name_ @ 2022-08-05 12:47:36

这道题有高精的部分，可以将语言转换成py

by dengyujie2020 @ 2022-08-05 12:50:11

而且这题数据太大，要用高精。如果只是单纯学DP，建议去做P1192 台阶问题

As we all know , 第i级台阶可以从第i-1 与第i-2级跳上来，故f[i]=f[i-1]+f[i-2] 初始值再赋值一下就行