滚动数组

示例练习>>>

一维滚动数组

滚动数组不是一种数据结构，他是一种算法优化思想，滚动数组的作用在于优化空间降低空间复杂度，每次使用固定的一些存储空间，比如我们常见的斐波那契数列：f[n] = f[n – 1] + f[n – 2] ，普通的写法如下：

// 1、1、2、3、5、8、13、21、34、……
private int fibonacci(int n) {// n>=0
    if (n == 0 || n == 1)
        return 1;
    int[] num = new int[n + 1];
    num[0] = 1;
    num[1] = 1;
    for (int i = 2; i <= n; i++)
        num[i] = num[i - 1] + num[i - 2];
    return num[n];
}

如下图所示，虽然定义一个很长的数组，但每次都用最近的 3 个，前面的都浪费了，所以我们可以使用滚动数组，只需要一个长度为 3 的数组即可。

private int fibonacci(int n) {// n>=0
    if (n == 0 || n == 1)
        return 1;
    int[] num = new int[3];// 只需要一个长度为 3 的数组即可。
    num[0] = 1;
    num[1] = 1;
    for (int i = 2; i <= n; i++)
        num[i % 3] = num[(i - 1) % 3] + num[(i - 2) % 3];
    return num[n % 3];
}

二维滚动数组

二维滚动数组相当于把二维数组用一维数组来代替，比如我们常见的背包问题《插入背包问题的链接》。

三维滚动数组

三维滚动数组相当于把三维数组用二维数组来代替，这个可以参考 Floyd算法 。

相关链接