`
128kj
  • 浏览: 600180 次
  • 来自: ...
社区版块
存档分类
最新评论

滚动数组

阅读更多
public class Main{
  public static void main(String args[]){
    //举个简单的例子:
    long d[]=new long[100];
    d[0]=1;d[1]=1;
    for(int i=2;i<100;i++)
       d[i]=d[i-1]+d[i-2];
     System.out.printf("%d\n",d[99]); 

  /* 上面这个循环d[i]只需要解集中的前2个解d[i-1]和d[i-2];
   为了节约空间用滚动数组的方法 */


   d=new long[3];
   d[0]=1;d[1]=1;
   for(int i=2;i<100;i++)
      d[i%3]=d[(i-1)%3]+d[(i-2)%3];
   System.out.printf("%d",d[99%3]);
 }
}



对于二维数组也可以用这种方法 例如:
long d[]=new long[100][100];
for(int i=1;i<100;i++)
  for(int 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];使用用滚动数组
long d[][]=new long[2][100];
for(int i=1;i<100;i++)
  for(int j=0;j<100;j++)
     d[i%2][j]=d[(i-1)%2][j]+d[i%2][j-1];

   滚动数组实际是一种节约空间的办法,时间上没什么优势,多用于DP中, 一个DP,平常如果需要1000×1000的空间,其实根据DP的特点,能以2×1000的空间解决问题, 并且通过滚动,获得和1000×1000一样的效果。


分享到:
评论

相关推荐

    滚动数组应用:POJ 1159

    标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...

    滚动数组在云计算和分布式系统中的应用.pptx

    ### 滚动数组在云计算和分布式系统中的应用 #### 一、滚动数组在云计算中的分布式存储 **1.1 滚动数组通过数据分片实现分布式存储** 滚动数组在分布式存储中扮演着关键角色,它通过将数据划分成较小的块(分片)...

    Java滚动数组计算编辑距离操作示例

    Java 滚动数组计算编辑距离操作示例 Java 滚动数组计算编辑距离操作是一个非常重要的技术,涉及到 Java 字符串与数组的遍历、计算、转换等相关操作技巧。编辑距离(Edit Distance),也称 Levenshtein 距离,是指由...

    9大背包问题详解9大背包问题详解

    优化方法包括简化状态转移方程和使用滚动数组优化空间复杂度。 问题3:多重背包问题 多重背包问题是指物品有多个副本的情况。解决思路是使用动态规划,定义状态转移方程,考虑物品的多个副本。优化方法包括转化为...

    leetcode刷题,数组部分(python)

    [二维数组](https://so.csdn.net/so/search?q=%E4%BA%8C%E7%BB%B4%E6%95%B0%E7%BB%84&spm=1001.2101.3001.7020)及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组...

    数组分割1

    为了实现空间复杂度的优化,可以采用滚动数组技术,将三维数组F[i][j][k]简化为二维数组F[j][k],因为i的值始终递增,无需保存所有i的历史状态。这将空间复杂度降低到O(N * Sum/2),其中N是序列的长度。 在找到最优...

    最长公共子序列

    其基本思想是建立一个二维数组LCS[len1+1][len2+1],其中len1和len2分别是两个字符串的长度。LCS[i][j]的值表示字符串1的前i个字符和字符串2的前j个字符的最长公共子序列的长度。初始化时,当i或j为0时,LCS[i][j]的...

    数字三角形最大路径

    用滚动数组实现最大路径问题

    数组—凑和 代码

    在编程领域,"凑和"通常...在实际应用中,还需要考虑优化算法,如剪枝操作以减少回溯法中的无效计算,或者使用滚动数组来降低动态规划的空间复杂度。同时,对于不同的问题规模和需求,可能需要灵活选择适合的解题方法。

    斐波那契数列.rar

    斐波那契数列的几种时间复杂度优化 以下代码因不同算法而时间复杂度不同个人归类为不同版本,总结...3.以下利用到了动态规划的滚动数组。 4.用位运算来代替乘法、除法以及取模。 5.有数学公式用数学公式@.@....

    NOIP2000年提高组解题报告

    4. 滚动数组:在解决乘积最大问题时,可以使用滚动数组来降低空间复杂度。 本文生成的知识点涵盖了进制转换、动态规划、高精度乘法、滚动数组等多个编程领域的知识点,对于编程爱好者和青少年信息学选手具有重要的...

    资源背包问题(c++)

    - **时间空间复杂度**:常规方法为O(N*V),使用滚动数组优化后空间复杂度可降低到O(V)。 2. **完全背包问题**: - **问题描述**:与01背包相似,但每种物品可以有无限数量。 - **特点**:每种物品可无限次放入...

    【ACM程序设计】动态规划 第二篇 LCS&amp;LIS问题.doc

    我们可以使用一个二维数组来存储状态d(i,j),然后使用滚动数组来优化空间。 现在,让我们来看LIS问题。给定一个序列,我们想找到最长上升子序列。为了解决这个问题,我们可以使用动态规划的方法。我们定义状态d(i)...

    2023年9月30日 上午 题解

    C++的二维动态规划数组可以有效地处理这个问题,同时滚动数组技术可以减少内存消耗。 T4的宿舍楼问题是一个基于图的最短路径问题,我们可以使用动态规划来求解。定义状态表示到达特定位置所需的时间,通过转移方程...

    最长公共子序列算法总结

    - **O(nlogn)算法**虽然在理论上的时间复杂度更高,但由于采用了滚动数组优化了空间复杂度,使其在实际应用中更加高效。 通过上述介绍可以看出,选择哪种算法取决于具体的应用场景和对时间和空间复杂度的要求。

    labview数组滚动

    labview实现2D数组滚动显示。

    WTongStudio#LeetCode#剑指 Offer 48. 最长不含重复字符的子字符串1

    代码实现(滚动数组优化)dp := 0 // 用一个值当做滚动数组使用i := -1 // i表示前面最近的s[j]==s[i]的位置if dp &lt; j-i {

    C++背包和完全背包讲解

    完全背包的一维滚动数组优化与01背包相似,但需要注意的是更新顺序应从后向前进行,避免更新过程中覆盖掉还未使用的值。 ```cpp #include using namespace std; int v[1005], w[1005], f[1005]; int main() { ...

    Roberry_house_dynamicprogramming_源码

    这被称为滚动数组优化。 总的来说,"Roberry_house_dynamicprogramming_源码"涉及的核心知识点包括: 1. 动态规划的基本概念和应用 2. 状态转移方程的建立 3. 数组和变量的使用来存储中间结果 4. 最优化问题的解决...

    LCS.rar_lcs 优化_lcs.cpp_positiongdm

    1. **滚动数组**:通过只保留上一行的状态来减小空间需求,这样只需O(min(m, n))的空间,其中m和n分别是两个字符串的长度。 2. **自底向上**:从短字符串到长字符串逐步求解,避免了从长向短回溯的过程,提高了效率...

Global site tag (gtag.js) - Google Analytics