滚动数组

蓝桥杯国赛快来了,赶快找来往届赛题瞅瞅先,看到最后一题,发现需要用到动态规划,但是感觉数据比较大,单纯的用动态规划怕是要超内存,怎么办呢?这时发现了一个新名词,最起码对我而言的新名词——滚动数组,顿时懵了,啥叫滚动数组?怎么个滚动发儿?
于是开始搜索资料,找到一个不错的解释。当然,最好的解释一定是代码了>>>

ACM模版

滚动数组

一维

int main()
{
    int i;
    long long d[80];
    d[0] = 1;
    d[1] = 1;
    for(i = 2; i < 80; i++)
    {
        d[i] = d[i - 1] + d[i - 2];
    }
    printf("%lld\n",d[79]);
    return 0;
}
上面这个循环d[i]只依赖于前两个数据d[i - 1]和d[i - 2]; 为了节约空间用滚动数组的做法。
int main()
{
    int i;
    long long d[3];
    d[0] = 1;
    d[1] = 1;
    for(i = 2; i < 80; i++)
    {
        d[i % 3] = d[(i - 1) % 3] + d[(i - 2) % 3];
    }
    printf("%lld\n", d[79%3]);
    return 0;
}
上面的取余运算,我们成功地只保留了需要的最后3个解,数组好象在“滚动”一样,所以叫滚动数组(对于二维也可以用)。所以,很明显,滚动数组可以通过取余(%)来实现的,但是这里存在一个通病,那就是时间换内存一定会牺牲时间。因此,滚动数组一般用在时间比较充裕,而内存不够的情况下。

二维

对于二维数组,我们可以这样子改造:

int i, j, d[100][100];
for(i = 1; i < 100; i++) for(j = 0; j < 100; j++) d[i][j] = d[i - 1][j] + d[i][j - 1];

上面的d[i][j]只依赖于d[i - 1][j], d[i][j - 1];
运用滚动数组

int i, j, d[2][100];
for(i = 1; i < 100; i++) for(j = 0; j < 100; j++) d[i % 2][j] = d[(i - 1) % 2][j] + d[i % 2][j - 1];

附录

附上另外一种滚动数组的写法(其实和取余一个路子):
斐波那契数列……

int Fib[3];

int fib(int n)
{
    Fib[1] = 0;
    Fib[2] = 1;
    for(int i = 2; i <= n; ++i)
    {
        Fib[0] = Fib[1];
        Fib[1] = Fib[2];
        Fib[2] = Fib[0] + Fib[1];
    }
    return Fib[2];
}

int main()
{
    int ncase, n, ans;
    scanf("%d", &ncase);
    while(ncase--)
    {
        scanf("%d", &n);
        ans = fib(n);
        printf("%d\n", ans);
    }
    return 0;
}
全部评论

相关推荐

我:“加班需要有加班工资。”&nbsp;hr:“为什么?”&nbsp;哈哈哈哈哈哈哈离大谱
juntenor:你确实太理想化了,对社会不了解呀。这个和HR没有关系,这是国内特色,不然怎么还会有外包就这种逆天的存在呢。
点赞 评论 收藏
分享
asdasdasda...:19岁,不容易啊可能升个本会好点,现在学历歧视太严重了
点赞 评论 收藏
分享
05-07 17:58
门头沟学院 Java
wuwuwuoow:1.简历字体有些怪怪的,用啥写的? 2.Redis 一主二从为什么能解决双写一致性? 3.乐观锁指的是 SQL 层面的库存判断?比如 stock > 0。个人认为这种不算乐观锁,更像是乐观锁的思想,写 SQL 避免不了悲观锁的 4.奖项证书如果不是 ACM,说实话没什么必要写 5.逻辑过期时间为什么能解决缓存击穿问题?逻辑过期指的是什么 其实也没什么多大要改的。海投吧
简历中的项目经历要怎么写
点赞 评论 收藏
分享
鼠鼠第一次实习,啥也不懂一直是自己一个人吃的饭,不会做工作老是被嫌弃,大人的世界是这样的吗?
我是星星我会发亮:好的mt有两种,一种愿意教你的,一种几乎什么活都不给你派让你很闲允许你做自己事情的
实习吐槽大会
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务