求符合条件的正整数序列的数量

Given2001

问题描述：

　　小明想知道，满足以下条件的正整数序列的数量：

　　1. 第一项为 n；

　　2. 第二项不超过 n；

　　3. 从第三项开始，每一项小于前两项的差的绝对值。

　　请计算，对于给定的 n，有多少种满足条件的序列。
输入格式：

　　输入一行包含一个整数 n。
输出格式：

　　输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
样例输入：

　　4
样例输出：

　　7
样例说明：

以下是满足条件的序列：
　　4 1
　　4 1 1
　　4 1 2
　　4 2
　　4 2 1
　　4 3
　　4 4
评测用例规模与约定：

　　对于 20% 的评测用例，1 <= n <= 5；
　　对于 50% 的评测用例，1 <= n <= 10；
　　对于 80% 的评测用例，1 <= n <= 100；
　　对于所有评测用例，1 <= n <= 1000。

我的疑问
以下是我的代码，纯粹通过递归暴力算的，问题就是数据一大，甚至n超过15都要算半天
有没有更好的办法，或者优化我的方法（本人萌新，代码写的烂大佬勿怪）

#include <iostream>
#include <cmath>

using namespace std;

int n;
int ret;
void ca(int a, int b)
{
    int ab = abs(a - b);
    int c;
    for (c = 1; c < ab; c++)
    {
        ret++;
        //cout << a << '\t' << b << '\t' << c << endl;
        ca(b, c);
        ret %= 10000;
    }
}
int main()
{
    cin >> n;
    ret = 0;
    for (int i = 1; i <= n; i++)
    {
        ret++;
        //cout << n << '\t' << i << endl;
        ca(n, i);
    }
    cout << ret << endl;
    return 0;
}

Given2001

研究了一晚上算是找到了点点规律，发出来大家共同学习=。=
（不一定对，有错误请大佬指正）
首先，我们先手算一下n为6时所有可能的序列（当然你也可以用代码）

6       1
6       1       1
6       1       2
6       1       3
6       1       3       1
6       1       3       1       1
6       1       4
6       1       4       1
6       1       4       1       1
6       1       4       1       2
6       1       4       2
6       1       4       2       1
6       2
6       2       1
6       2       2
6       2       3
6       3
6       3       1
6       3       1       1
6       3       2
6       4
6       4       1
6       4       1       1
6       4       1       2
6       5
6       6

我们可以发现：
当 4 1 的后面分支都是相同的（我也表达不明白，看图）
可以得出：
当前一个数(a)和后一个数(b)相同时，产生的结果数也是相同的
于是我们将结果数保存在一个二维数组中，下一次要用时直接取用
经过测试，有效的减少了运算量，对于n=1000也能1s内得出结果
（虽然我也不知道答案是否准确就对了，希望有做出不同思路的大佬能跟我校对下答案）
贴下我优化后的代码

#include <iostream>
#include <cmath>
//#include <ctime>

using namespace std;

int buff[1001][1001];
//clock_t clSt, clEd;

int ca(int a, int b)
{
    if (buff[a][b] != 0) {
        //由于ab相同后续的可能性也相同，这里我直接取用之前保存的结果数
        return buff[a][b];
    }
    int ab = abs(a - b);
    int c;
    int count = 1;
    for (c = 1; c < ab; c++)
    {
        //cout << a << '\t' << b << '\t' << c << endl;
        count += ca(b, c);
    }
    count %= 10000;//每次都对结果取余，防止溢出（可能。。。还是会溢出）
    buff[a][b] = count;//保存结果
    return count;
}
int main()
{
    int n;
    cin >> n;
    //初始化
    //clSt = clock();
    int ret = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            buff[i][j] = 0;
        }
    }
    //第二个数
    for (int i = 1; i <= n; i++)
    {
        //cout << n << '\t' << i << endl;
        ret += ca(n, i);
    }
    ret %= 10000;
    //clEd = clock();
    cout << ret << endl;
    //double runtime = (double)(clEd - clSt) / CLOCKS_PER_SEC; 
    //cout << "用时：" << runtime << endl;
    return 0;
}

Given2001

2020年3月29日12:50:34 我又回来了
竞赛老师已经讲解了这道题，看到老师的代码，我……

话不多说，先上代码

#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>

using namespace std;

int N;
const int MOD = 10000;
int mem[1001][1000];

int dfs(int pre, int cur) {
    if (cur <= 0) return 0;
    if (mem[pre][cur] != 0) return mem[pre][cur];
    return mem[pre][cur] =
               (1 + dfs(pre, cur - 1) + dfs(cur, abs(pre - cur) - 1)) % MOD;
}

void work() {
    cin >> N;
    cout << dfs(N, N) << endl;
}

int main() {
    int a = clock();
    work();
    int b = clock();
    clog << (b - a) << "ms" << endl;
    return 0;
}

思路就是在我之前的优化代码上进一步优化。
原本递归函数中研究的是a与b所得出的结果数目
也就是说再最极端的情况下（记忆数组被填满）
我们需要运算结果1000*1000次，
再加上main函数里的一层循环
就是1000*1000*1000次，这时候我们就要考虑把最外层的循环给去掉
也就是把递归研究的问题转换为a与1~b所得出的结果总数
这样即使记忆数组被填满，也只有1000*1000次计算
大概是这样……

测试结果
14ms解决战斗！！
平均12ms就可以
原文地址

winsome8538

也不会 坐等大神回复

墨羽岚

一点都不萌新

V流年V

冒个泡

珂乔乔

跟大佬学习一下

如果孤独感

大佬，敬仰

如果孤独感

大佬

Given2001

没有大佬来验证下我的思路吗。。。

Given2001

墨羽岚 发表于 2020-3-16 17:13
一点都不萌新

我是货真价实的萌新啊，大佬可能根本不会考虑枚举把不懂大佬的世界

依可儿

完全看不懂，等大神指教

乔珂珂

枚举法行不。。。虽然很麻烦

Given2001

乔珂珂 发表于 2020-3-27 11:37
枚举法行不。。。虽然很麻烦

我一开始的方法就是枚举啊，emmm你指的枚举是啥

烟肖雨晨

为什么数学界的小明也跑到编程界来了
纯属冒个泡，但这道题还真不会

Given2001

烟肖雨晨 发表于 2020-3-27 14:53
为什么数学界的小明也跑到编程界来了
纯属冒个泡，但这道题还真不会

小明是个神秘的人物

wuhao4221961

谢谢谢谢

bailean

一点都不萌新

乔珂珂

学习一下~
~~

Given2001

墨羽岚 发表于 2020-3-16 17:13
一点都不萌新

老师的标准答案出来了，有兴趣看看嘛