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一样的效果。
分享到:
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1757060
主要介绍了Java滚动数组计算编辑距离操作,涉及java字符串与数组的遍历、计算、转换等相关操作技巧,需要的朋友可以参考下
[二维数组](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.《算法设计技巧与分析》的课堂内容c源码实现 2.编译环境vc6.0 3.关键代码有详细的注释描述
用滚动数组实现最大路径问题
斐波那契数列的几种时间复杂度优化 以下代码因不同算法而时间复杂度不同个人归类为不同版本,总结...3.以下利用到了动态规划的滚动数组。 4.用位运算来代替乘法、除法以及取模。 5.有数学公式用数学公式@.@....
代码实现(滚动数组优化)dp := 0 // 用一个值当做滚动数组使用i := -1 // i表示前面最近的s[j]==s[i]的位置if dp < j-i {
labview实现2D数组滚动显示。
题目:309. 最佳买卖股票时机含冷冻期滚动数组:
tag上是分层图+矩阵优化,但是被我用暴力+滚动数组水过去了(赞美O2!)对每个点有三种状态,0:上一秒已经在这个城市了;1:这一秒刚到;2:自爆。只需要记录最后时刻0、1的和以及所有时刻2的和即可,注意滚动数组...
最长公共子序列的两种算法简介,一种是平时最常见的算法,还有一种用滚动数组来做的。
二分法、回溯法、剪枝DFS、BFS、动态规划、位运算、数学、大数、排列有限状态自动机、排序、归并排序、归并思想、滚动数组优化、双指针、分治法二叉树遍历、问题抽象、递归、俄罗斯农民乘法、滑动窗口、约瑟夫环、双...
javascript读取json数组生成滚动分页 javascript读取json数组生成滚动分页 javascript读取json数组生成滚动分页
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 题解 数组篇 二. 字符串 题目分类 题
CC--面试问题来自各种编程专家的算法问题的解决方案,包括LeetCode,LintCode和Hackerrank(过去的Interview Street)。LeetCode示例std:sort +自定义cmp: 。... DP:通过滚动数组进行优化: 。 DP:最小解
二维数组及滚动数组: 118, 119, 661, 598, 419 数组的旋转: 189, 396 特定顺序遍历二维数组: 54, 59, 498 二维数组变换: 566, 48, 73, 289 前缀和数组: 303, 304, 238 字符串 位运算 栈与递归 链表 哈希表 贪心算法 ...
1.4.二维数组及滚动数组 题号 描述 状态 1.5.数组的旋转 题号 描述 完成状态 1.6.特定顺序遍历二维数组 题号 C++11 完成状态 1.7.二维数组变换 题号 描述 完成状态 1.8.前缀和数组 题号 描述 完成状态 模板题-前缀和...
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 二. 字符串 题目分类 题目编号 字符 520 回文串的...
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 链表类: 文章:https://mp.weixin.qq.com/s/vK0JjSTHfpA
二维数组及滚动数组 118、119、661、598、419 数组的旋转 189、396 特定顺序遍历二维数组 54、59、498 二维数组变换 566、48、73、289 前缀和数组 303、304、238 题解 数组篇 二. 字符串 题目分类 题目编号 字符 ...