滚动数组

一维数组

老生常谈的斐波那契数列。 1 1 2 3 5 8 13 21 .... 编写一个函数，输入n，返回第n个数(n <= 50)。(实测当 n = 47 爆int)

// 不使用滚动数组
LL fib(int n)
{
    LL fibnacci[55];
    fibnacci[0] = fibnacci[1] = 1;
    
    if (n == 0 || n == 1) return 1;

    for (int i = 2; i <= n; i++)
        fibnacci[i] = fibnacci[i - 1] + fibnacci[i - 2];

    return fibnacci[n];
}

// 使用滚动数组
// 在求第n个数时，只用到了前面两个值，所以只需开一个长度为三的数组。
LL fib(int n)
{
    LL fibnacci[3];
    fibnacci[0] = fibnacci[1] = 1;

    if (n == 0 || n == 1) return 1;

    while (n - 1)
    {
        n--;
        fibnacci[2] = fibnacci[0] + fibnacci[1];
        fibnacci[0] = fibnacci[1];
        fibnacci[1] = fibnacci[2];
    }

    return fibnacci[2];
}

二维数组

递推关系f[i][j] = f[i - 1][j] + f[i - 1][j - x] (其中 x > 0)

编写一个函数，输入a，b，输出f[a][b]。(i, j <= 50)

// 不使用滚动数组
// 第0行与第0列为递推的出口
int f[50][50], x = 2;

void init()
{
	for (int i = 0; i < 50; i++)
		f[0][i] = 1;
}

int func(int a, int b)
{
	init();
	for (int i = 1; i <= a; i++)
		for (int j = 1; j <= b; j++)
			if (j >= x) f[i][j] = f[i - 1][j] + f[i - 1][j - x];
	return f[a][b];
}

// 使用滚动数组
// 在求f[i][j]时只用到了前面一行所以可以使用滚动数组
int f[2][50];

void init()
{
    for(int i = 0; i < 50; i++)
        f[0][i] = 1;
}

int func(int a, int b)
{
    init();
    for (int i = 1; i <= a; i++)
    {
        for (int j = 0; j < 50; j++) f[i % 2][j] = 0; // 这个地方很重要 一开始我没有想到 打印时才发现问题
        for (int j = 1; j <= b; j++)
            if (j >= x) f[i % 2][j] = f[1 - i % 2][j] + f[1 - i % 2][j - x]; // 第1行使用第0行，第0行使用第1行
    }
    return f[a % 2][b];
}