精华内容
下载资源
问答
  • 主要介绍了Java滚动数组计算编辑距离操作,涉及java字符串与数组的遍历、计算、转换等相关操作技巧,需要的朋友可以参考下
  • 滚动数组(简单说明)

    千次阅读 多人点赞 2021-02-24 14:21:51
    首先呢,滚动数组是一种能够在动态规划中降低空间复杂度的方法, 有时某些二维dp方程可以直接降阶到一维,在某些题目中甚至可以降低时间复杂度,是一种极为巧妙的思想, 简要来说就是通过观察dp方程来判断需要使用...

    前提概要

    首先呢,滚动数组是一种能够在动态规划中降低空间复杂度的方法
    有时某些二维dp方程可以直接降阶到一维,在某些题目中甚至可以降低时间复杂度,是一种极为巧妙的思想,
    简要来说就是通过观察dp方程来判断需要使用哪些数据,可以抛弃哪些数据,
    一旦找到关系,就可以用新的数据不断覆盖旧的数据量来减少空间的使用,
    接下来我会介绍一些简单例题来具体解释一下滚动数组的作用。

    先以斐波那契数列为例
    我们先以斐波那契数列来简单感受一下滚动数组的魅力,先上一段经典的代码(使用滚动数组)

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	int a[37];
    	a[0]=1;
    	a[1]=1;
    	//求斐波那契数列第37个数
    	for(int i=2;i<=36;i++){
    		a[i]=a[i-1]+a[i-2];
    	}
    	printf("%d\n",a[36]);
    	return 0;
     
    } 
    
    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[3];
        a[0] = 1;
        a[1] = 1;
        for(int i = 1;i <= 35;i++)
        {
            a[2] = a[0] + a[1];
            a[0] = a[1];
            a[1] = a[2];
        }
        printf("%d\n",a[2]); 
        return 0;
    }
    

    通过观察斐波那契数列方程 f(n)= f(n-1)+ f(n-2),我们可以发现,
    我们实际上只需要前两个递推的数求和即可,于是我们可以使用数组的前三个位置来分别存贮数据, 待计算完之后,再用新的数据将旧数据覆盖。
    这样我们 本来需要用三十多个位置的数组,最终却只用了三个位置, 大大减少了空间复杂度。
    对于某些只需要最终答案的题目,我们可以抛弃掉当中一些不必要存贮的数据,来减少空间的使用。

    再以0/1背包为例

    这里我们以HDU2602的bone collector题目为例子,
    对于每一个状态,我们都可以判断这次是取还是不取或是取不下。
    枚举第i个物品,枚举j代表背包可以放的下的体积。
    若不取或者取不下,那么结果就是dp[i-1][j],
    若取,就由前面的状态预留出weight[i]的位置再加上i物品的价值,即dp[i-1][j-weight[i]]+value[i]。

    可得二维dp方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
    我们先来看二维的dp矩阵,
    背包价值是{1,2,3,4,5},对应的体积是{5,4,3,2,1};
    在这里插入图片描述
    以dp[4][j]->dp[5][j]为例,此时第5个物品的体积为1,价值为5
    在这里插入图片描述
    我们可以清楚的看出来,dp方程递归过程是不断地由上一行的数据传递到下一行,
    比如最后dp[5][10]是由dp[5][10]=max(dp[4,10],dp[4,9]+5))=14推得的,
    也就是说当我们递推到dp[i][j]时,对于那些只要求最终最佳答案的题目来说,只需要i-1这行的数据即可,至于上面的i-2,i-3都是不需要的数据,
    题目如果并没有要求中间的状态(比如输出背包的方案),我们就可以将其省略来节省空间的使用。
    所以我们可以只用一维数组dp[j]来记录数据dp[i][j]的状态,在更新的过程中不断用新的数据dp[j] (dp[i][j]) 覆盖掉旧的数据dp[j](dp[i-1][j])。

    为什么j维度在01背包是逆序,完全背包是正序呢

    • 我相信会有很多同学对01背包第二维j为什么是倒着递推有疑惑。
      我们从正序进行,假设当i=5,j=9时,那么此时dp[9]是由前面的dp[8]和dp[9]递推更新,那么现在dp[9]实际上存贮的是递推得到的dp[5][9]而并非旧数据dp[4][9],那么也就不能保证dp[5][10]的递推成功(dp[5][10]正确值应该是由dp[4][10]和dp[4][9]递推得到的) ,但正序的做法却意味着可以多次调用前面的数据,相当于多次取用物品,也就是完全背包(物品可取次数为无限次)的思路了。
    • 那该怎么确保不覆盖dp[9]存贮的数据dp[4][9]呢,那么倒序就起作用了。假设当i=5,j=10时,dp[10]内的数据存贮的是dp[4][10]的数据,由于j从尾部开始枚举,dp[10]就会由dp[9]和dp[10]递推得到(dp[9]存贮的是dp[4][9],dp[10]存贮的是dp[4][10]),那么此时dp[10]的值就更新为了dp[5][10]。然后依次类推,因为是倒序的缘故,那么接下来枚举的j都要比先前的j要来的小,所以当某个位置更新数据时,并不会调用其位置后面的数据,一定会是先调用其位置之前的旧数据,然后再将当前位置更新覆盖掉原来的旧数据,也就保证了数据更新的有序性。

    小结

    对于动态规划题目来说,我们可以先写出最原始的dp方程,再通过观察dp方程,使用滚动数组进行优化,我们需要思考如何更新数据和覆盖数据来达到降维的目的(可能需要很长的时间思考,不过熟能生巧)。

    具体代码解析

    #include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e3+10;
    int t,n,v;
    int dp[maxn];
    int value[maxn];
    int weight[maxn];
    int main()
    {
        scanf("%d",&t);
        while(t--)
        {
            memset(dp,0,sizeof dp);
            scanf("%d %d",&n,&v);
            for(int i = 1;i <= n;i++)
                scanf("%d",&value[i]);
            for(int i = 1;i <= n;i++)
                scanf("%d",&weight[i]);
            // for(int i = 1;i <= n;i++)	原始二维dp方程
            //     for(int j = 0;j <= v;j++)
            //     {
            //         if(j >= weight[i])		//若取得下,则可以选择取或不取
            //             dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
            //         else	
            //             dp[i][j]=dp[i-1][j];
            //     }
            for(int i = 1;i <= n;i++)	//使用滚动数组优化后的dp方程
                for(int j = v;j >= weight[i];j--)	//倒序保证数据更新的有序性,保证只取一次,正序则是完全背包的写法
                    dp[j]=max(dp[j],dp[j - weight[i]] + value[i]);
            printf("%d\n",dp[v]);
        }
        return 0;
    }
    
    
    
    展开全文
  • 滚动数组应用:POJ 1159

    2019-04-15 01:20:41
    NULL 博文链接:https://128kj.iteye.com/blog/1757060
  • 这篇文章继续在前一篇文章的基础上介绍动态规划数组的优化方式。很多基础算法本来都是写给我家的小少年看的,结果发现后浪学习的速度远远超出我的想象,在一个周末用这篇文章来纪念一下吧。

    这篇文章继续在前一篇文章的基础上介绍动态规划数组的优化方式。很多基础算法本来都是写给我家的小少年看的,结果发现后浪学习的速度远远超出我的想象,在一个周末用这篇文章来纪念一下吧。


    斐波那契数列

    斐波那契数列:
    f(n) = f(n-1) + f(n-2) (n>1)
    f(0) = 1
    f(1) = 1

    dp数组方式实现

    int fibonacci(int n) {
        if (n == 0 || n == 1) return dp[n]=1;
        if (dp[n] != -1) return dp[n];
        return dp[n]=fibonacci(n-1)+fibonacci(n-2);
    }
    

    详细可参看:https://liumiaocn.blog.csdn.net/article/details/109397755


    计算次数的证明

    自从发现少年已经自己会用spfa这样的东西来解决问题之后,这种基础的内容应该就不能发给他看了,所以简单确认了一下动态规划法到底解决了什么问题,为什么实际上加法的执行次数是fibonacci(n)-1,结果二十分钟左右用归纳法就证明完了,除了结尾的fib(n)-1应该是fib(n+1)-1,基本似乎是对的。
    在这里插入图片描述


    动态规划法解决

    后浪看完给他写的基础教程,说这还可以用滚动数组优化一下,给了个图,使用Java方式1ms计算的斐波那契45的计算结果。
    在这里插入图片描述


    滚动数组的使用

    • 第一种方式:使用&1
    #define FIBONACCI_MAX 2
    int dp[FIBONACCI_MAX] = { 0 };
    
    int fibonacci(int n) {
        dp[0]=1,dp[1]=1;
        for (int i=2; i<=n; i++) dp[i&1] = dp[(i-1)&1] + dp[(i-2)&1];
        return dp[n&1];
    }
    

    代码说明:和1进行&的操作,只会有0和1两个下标,因为此示例中使用的情况在求解的时候只是用到了n-1和n-2,这种大概是最节省的做法了,将本来长度为n的空间降到常量2.


    • 第二种方式:使用求余
    #define FIBONACCI_MAX 2
    int dp[FIBONACCI_MAX] = { 0 };
    
    int fibonacci(int n) {
        dp[0]=1,dp[1]=1;
        for (int i=2; i<=n; i++) dp[i%FIBONACCI_MAX] = dp[(i-1)%FIBONACCI_MAX] + dp[(i-2)%FIBONACCI_MAX];
        return dp[n%FIBONACCI_MAX];
    }
    

    代码说明:和第一中方式如出一辙,但是由于第一种和1进行&的情况只有两种状态,虽然可以解决大部分问题,但是如果有三个状态需要使用的情况就会比较困难,可以考虑使用%,本质上是确认滚动时到底需要几个元素进行运算。


    总结

    看到一个之前从来没有接触过计算机的少年在繁重的大学课程学习之余1个月不到的时间从对编程一无所知到可以较为熟练使用Java和C进行滚动数组/常见排序/邻接矩阵/最短路径等算法进行实现,觉得很是欣慰和开心,真心感觉计算机算法教育实际应该从初高中开始执行比较好。

    展开全文
  • 三种背包问题+滚动数组优化

    多人点赞 2020-07-14 22:51:01
    三种背包问题+滚动数组优化 文章目录 滚动数组 01背包 二维数组 滚动数组 优化版 完全背包 二维数组 滚动数组 优化版 多重背包 二维数组 滚动数组 二进制优化 滚动数组 滚动数组简单的理解就是让数组滚动起来,起到...

    三种背包问题+滚动数组优化

    滚动数组

    滚动数组简单的理解就是让数组滚动起来,起到节省存储空间的作用。主要应用在递推或动态规划中。

    举个适合使用滚动数组的例子:
    斐波那契数列为1、1、2、3、5、8、13、21、34……此数列从第3项开始,每一项都等于前两项之和。
    递推公式为F(n)=F(n-1)+F(n-2),n≥3,F(1)=1,F(2)=1。

    假如我们要求斐波拉切数列的第80项,我们常规的方法是定义一个80大小的数组,然后进行如下的循环。

    在这里插入图片描述

    那么我们要求第2e7项的斐波拉契,我们不可能去定义一个2e7的数组。通过观察,我们可以发现其实每一次循环都只用到前两位的数组,使用过后就不会使用了,很浪费空间。我们可以使用滚动数组来解决。

    使用滚动数组的话,我们就只需要定义一个3大小的数组(仔细想想我们滚动话只需要3个数就够了)。

    在这里插入图片描述

    滚动数组的使用重在对于取余(%)的理解下面来演示一下。

    无论多大的数取余某个数时,得到的数都在0到这个数之间。当下标对循环长度取余,则对于n长度的环,第n-1个的下一个将会是第0个,从而实现了循环。

    在这里插入图片描述
    在这里插入图片描述
    滚动数组只能节约空间复杂度,时间复杂度还是和原来一样。

    01背包

    描述:
    有n件物品和一个容量为m的背包。第i件物品的费用是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

    状态转移方程:

    二维数组

    用 dp[i][j]表示前i种物品放入一个容量为j的背包的最大价值
    dp[i][j]=j<w[i]? dp[i-1][j]:max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); (1<=i<=n,0<=j<=m)

    在这里插入图片描述
    下面通过图表样例理解下
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    此时我们可以发现我们得到了这么一个数组,dp[i][j]即表示在前i个物品中选取任意物品装填承重j背包时可得到的最大价值和。

    通过对上面图表的分析理解我们发现,我们只需要前两行的值就能得出新的一行,和斐波拉契很相似,我们可以使用滚动数组。

    滚动数组

    代码解析:
    在这里插入图片描述
    但是仅仅滚动数组的优化通常来说是不够的。毕竟不管怎么样还是一个二维数组,优化始终是有限的。

    优化版

    用dp[j]表示当前总重量为j的所有方案中的最大价值
    dp[j]=max(dp[j],dp[j-w[i]]+v[i]); (1<=i<=n ,w[i]<=j<=W)

    代码解析:
    在这里插入图片描述

    这里的一维数组的优化是最优的。

    核心是基于一维数组做反向迭代,这样的话j<w[i]的部分直接不用复制了,且由于是反向的线性更新也不会发生冲突。

    举个例子

    在这里插入图片描述

    在这里插入图片描述
    结合动图理解这里的反向迭代的巧妙。

    完全背包

    描述:
    N种物品,第i种的物品重量是w[i],价值是v[i],每种物品有无限件,求总重量在背包承重m以内的最大总价值。

    状态转移方程:

    二维数组

    用dp[i][j]表示前i种物品放入一个容量为j的背包的最大价值类似于简化为01背包。
    dp[i][j] = max(dp[i][j], dp[i-1][j-kw[i]] + kv[i]]) (1<=i<=n,0<=j<=m) (0 <= k*w[i] <= j)

    代码解析:

    在这里插入图片描述

    这里可以理解为变相的01背包,重量为kw[i],价值为kv[i]。

    小优化版:用dp[i][j]表示前i种物品放入一个容量为j的背包的最大价值,
    dp[i][j] = max(dp[i-1][j],dp[i][j-w[i]+v[i]) (1<=i<=n,0<=j<=W)

    代码解析:

    在这里插入图片描述

    核心在于将已装载的dp[i][j]用于后续dp,因为物品无限件,同一物品可以选取多次。这是其与01背包的主要区别。

    01背包 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    完全背包 dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

    这个已装载怎么理解?
    举个例子:
    遍历到第5个物品,其重量是3:
    那么dp[5][3]处在此次迭代中会存: 以3容量的背包选取前4种物品 和 选取一个桃子后以0容量的背包选取前四种物品中的最优情况。dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]);

    如果此时选择第5个的情况是最优情况,被存储了,那就表示已装载。因为能在后续的遍历中多次拿到第5个物品。

    如果已经dp[5][3]拿到了第5个物品那么在后续的dp[5][6]只需要存: 以6容量的背包选取前4种物品 和 再拿一个第5个物品加上dp[5][3]中的最优情况。


    看一下和01背包的区别
    在01背包中:
    假如遍历到第5个物品,其重量是3:
    那么dp[5][3]在此处迭代会存:以3容量的背包选取前4种物品 和 选取一个桃子后以0容量的背包选取前四种物品中的最优情况。dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    而dp[5][6]则是存以6容量的背包选取前4种物品 和 (以3容量的背包选取前4种物品+一个第5中物品的价值)的最优情况。
    dp[5][6]与dp[5][3]没有直接的迭代关系。

    滚动数组

    完全背包的滚动数组和01背包类似。

    代码解析:
    在这里插入图片描述
    但是仅仅滚动数组的优化通常来说是不够的。

    优化版

    用dp[j]表示当前总重量为j的所有方案中的最大价值
    dp[j]=max(dp[j],dp[j-w[i]]+v[i]); (1<=i<=n,0<=j<=W)

    代码解析:
    在这里插入图片描述

    核心在于类似01背包的反向迭代

    举个例子

    在这里插入图片描述

    在这里插入图片描述

    结合01背包的动图,理解其区别。

    多重背包

    描述
    有n种物品,第i种物品的重量是w[i],价值是w[i],每种物品的数量有限k[i],如何在m重量内,让总价值尽可能最大。

    普通的二维解法和完全背包很类似。

    二维数组

    代码解析:

    在这里插入图片描述

    这里与完全背包唯一不同的就是不但要满足背包大小,还要满足物品个数。

    滚动数组

    滚动数组多重背包

    代码解析:

    在这里插入图片描述

    二进制优化

    这里三个for循环复杂度太高,不适合很多题目,我们要进行优化。

    首先我们要知道我们的目的是什么,目的是将单种物品分解为概念上的多个不同物品然后做01背包。而且分解不是乱分解的,我们需要做到首先不能重复,其次需要将所有的分解的情况都要表示出来,比如有10个x物品,我们需要把0-10的组合情况全部都能表示出来。

    优化解法 (二进制优化)
    1.如果限制的数量*物品容量>=当前最大容量
    直接考虑成完全背包问题来处理,把物品数量当成无限数量来考虑。

    2.如果限制的数量物品容量<当前最大容量
    将单种物品二进制分解为概念上的多个不同物品然后做01背包
    *

    普通情况直接完全背包很好理解,特殊的二进制分解我们可以根据例子来理解:

    假如给了我们 价值为 2,但是数量却是10 的物品,我们应该把10给拆开,要知道二进制能够表示任何数的,所以10 就是可以有1,2,4,8之内的数把它组成,一开始我们选上 1了,然后让10-1=9,再选上2,9-2=7,在选上 4,7-4=3,而这时的3<8了,所以我们就是可以得出 10由 1,2,4,3来组成。

    我们能发现1,2,3,4能组成1-10以内的任何数。

    那么他们的价值是什么呢,是2,4,6,8,也就说给我们的价值为2,数量是10的这批货物,已经转化成了价值分别是2,4,6,8元的货物了,那么最后在进行dp选择的时候,就能通过他们的最优解选择,组成出我们需要的组成物品。形成概念上的01背包。

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 动态规划之滚动数组

    2021-11-05 18:28:41
    实际上,滚动数组应用的条件是基于递推或递归的状态转移中,反复调用当前状态前的几个阶段的若干个状态,而每一次状态转移后有固定个数的状态失去作用。滚动数组便是充分利用了那些失去作用的状态的空间填补新的状态...

           实际上,滚动数组应用的条件是基于递推或递归的状态转移中,反复调用当前状态前的几个阶段的若干个状态,而每一次状态转移后有固定个数的状态失去作用。滚动数组便是充分利用了那些失去作用的状态的空间填补新的状态,一般采用求模(%)的方法来实现滚动数组。

            举个求斐波那契数列的例子吧。其中采用了一个dp数组,实际上可以改为只使用dp[0]、dp[1]、dp[2]这3个元素空间,采用求模来实现。对应的算法如下:

    int Fib()
    {
        int dp[3];
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 3;i <= n;i++)
        {
            dp[i % 3] = dp[(i - 2) % 3] + dp[(i - 1) % 3];
        }
        return dp[n % 3];
    }

         例题:一个楼梯有n个台阶,上楼可以一步上一个台阶,也可以一步上两个台阶,求上楼梯共有多少种不同的走法。

         思路:设f(n)表示上n个台阶的楼梯的走法数。显然f(1) = 1,f(2) = 2(一种走法是一步上一个台阶,走两步,另外一种走法是一步上两个台阶).

                 对于大于2的n个台阶的楼梯,一种走法是第一步上一个台阶,剩余n-1个台阶的走法数是f(n-1);另外一种走法是第一步上两个台阶,剩余n-2个台阶的走法数是f(n-2),所以有f(n)=f(n-1)+f(n-2)。对应的状态转移方程如下:

      f(n)=\begin{cases} 1,n=1\\2,n=2\\f(n-1)+f(n),n>2\end{cases}    或者f(n)=\begin{cases} 1,n=0\\2,n=1\\f(n-1)+f(n-2),n > 1\end{cases}

    用一维动态规划数组dp[n](下标从0开始)存放f(n+1)(下标从1开始).采用左边的状态转移方程。对应的求解算法如下:

    int solve()
    {
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;i < n;i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }
    

            但dp[i]只与dp[i-1]和dp[i-2]两个子问题解相关,共3个状态,所以采用滚动数组,将dp数组设置为dp[3],对应的完整程序如下:

    #include <iostream>
    using namespace std;
    //问题表示
    int dp[3];
    int solve1()
    {
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;i < n;i++)
        {
            dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3];
        }
        return dp[(n - 1) % 3];
    }
    void main()
    {
        n = 10;
        cout << solve1(3) << endl;//输出结果为89
    }

            其他二维数组及高维数组也可以做这样的改进。例如,一个采用普通方法实现的算法如下:

            

    void solve()
    {
        int dp[MAX][MAX];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i < MAX;i++)
        {
            for(int j = 1;j < MAX;j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

            若MAX为1000,上面的方案需要1000 * 1000的空间,而dp[i][j]只依赖于dp[i-1][j]和dp[i][j-1],所以可以使用滚动数组,对应的算法如下:

            

    void solve1()
    {
        int dp[2][MAX];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i < MAX;i++)
        {
            for(int j = 0;j < MAX;j++)
            {
                dp[i % 2][j] = dp[(i - 1) % 2] + dp[i % 2][j - 1];
            }
        }
    }

            改用滚动数组后仅仅使用了2 * 1000的空间就获得1000 * 1000空间相同的效果。

    展开全文
  • 01背包进阶 二维数组/滚动数组 模/滚动数组 异或/一维数组 以1267:【例9.11】01背包问题为例 枚举所有物品能想到,但编写就很困难了。故需寻求01背包固定算法 1.二维数组写法 #include <stdio.h> int f...
  • 背包问题-01背包之滚动数组【动规五步法】 文章目录背包问题-01背包之滚动数组【动规五步法】0 - 前言1 - 滚动数组的由来2 - 动规五步法 0 - 前言 本文是参考【代码随想录】大佬的【背包专题】,受益匪浅,上一个...
  • 滚动数组是DP中的一种编程思想。简单的理解就是让数组滚动起来,每次都使用固定的几个存储空间,来达到压缩,节省存储空间的作用。起到优化空间,主要应用在递推或动态规划中(如01背包问题)。因为DP题目是一个自底...
  • 动态规划空间优化之滚动数组

    千次阅读 多人点赞 2019-08-06 20:30:15
    动态规划本就是一个记录再利用的高效算法,由于其要记录之前的状态,必然会使用大量空间,要优化动态规划算法的空间,我们必然要合理利用dp数组,有一种优化方法就是利用滚动数组来进行状态转移。 我们拿动态规划中...
  • 滚动数组

    2017-08-23 08:45:00
    这种方法很简单 可以防止内存过大 就是在 要的结果只和上一步有关的时候(类似情况)那之前的东西是没用处的 那只需新的盖旧的 然后算新的 重复 转载于:https://www.cnblogs.com/-Finch-/p/7416364.html...
  • 【LeetCode 0-Start】[数组]二维数组及滚动数组 文章目录前言一、[简单]118. 杨辉三角java代码二、[简单]119. 杨辉三角 IIjava代码三、[简单]661. 图片平滑器java代码四、[简单]598. 范围求和 IIjava代码五、[中等]...
  • 二维数组 如上图,一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。 问总共有多少...
  • 注意到这个二维数组的下一行的值,只用到了上一行的正上方和左边的值,因此可用滚动数组的思想,只要一行即可。 既然是要用正上方和左边的值,那么从右边开始依次求值,并覆盖在正上方的位置即可 01背包问题...
  • 滚动数组求解0/1背包问题(此处仅求装入背包的最大价值) // 由于第i个阶段(考虑物品i)的解dp[i][ * ]只与第i-1个阶段(考虑物品i-1)的解dp[i-1][ * ]有关,这种情况下保存更前面的数据已经毫无意义。 因此可以...
  • 01背包进阶到多重背包 二维数组/滚动数组 模/滚动数组 异或/一维数组/一维数组 优化 以1269:【例9.13】庆功会为例。 1.仿01背包思路,二维数组 #include <stdio.h> int n,m,v[505],w[505],s[505],f[505...
  • 滚动数组详解

    千次阅读 2017-07-26 15:31:24
    详细介绍滚动数组的原理以及优势,使用方法。
  • 如果是按上面的做法,空间大小可能会很大了,然而对于第x个数字,我们只需要知道x-1和x-2就可以了于是我们这里就引入滚动数组优化。 什么是滚动数组滚动数组就是根据数组的特点(一般是对成品代码进行修改)进行...
  • 但是本题中似乎不能像之前那样简单地利用“滚动数组”的思想来进行空间优化,因为在状态转移方程中用到了 dp[i-1][j-1],而如果利用“滚动数组”的话,这个值往往会被前一次 dp 元素的计算结果所覆盖,所以不大方便...
  • 定义 dp[j]是从物品0到i中挑选物品...一维滚动数组法 for(int i = 0; i < weight.size(); i++) for(int j = bag_size; j >= 0; j--) { if(j < weight[i]) dp[j] = dp[j-1]; else dp[j] = max(dp[j
  • 一个串和自己的反串最长...要用到滚动数组 #include<string.h> #include<iostream> using namespace std; const int maxN = 5010; int dp[2][maxN]; int N; char a[maxN]; char reverseA[maxN]; int ...
  • 滚动数组顾名思义就是让数组滚起来,是一种用时间去换空间的想法,往往在时间充足,空间超限的情况下适用。 滚动数组基本上都是在动态规划DP和递推中使用,大部分都是通过数组中的值结合其他的数更新数组中的某一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 98,911
精华内容 39,564
关键字:

滚动数组