本文主要介绍了将二维数组优化为一维数组的算法逻辑本质。 测试链接 : https://www.luogu.com.cn/problem/P1048
引言
当遇到时间转空间的问题时(dp, 背包问题, 子数组累加和等)，我们可以将一维数组优化为变量, 将二维数组优化为一维数组, 将三维数组优化为二维数组, 以此类推。
其中二维数组转一维数组最为常见, 因此本文将从二维数组优化为一维数组的算法逻辑本质出发, 介绍如何将二维数组优化为一维数组。
二维数组为什么要优化为一维数组
将二维数组优化为一维数组, 从而使空间复杂度从O(n * m)减少到O(m) 或 O(n), 提高程序空间利用率, 在数据量和数值较大时, 可以大大节省空间和磁盘I/O读写时间, 提高程序运行效率。
二维数组为什么能够转换为一维数组
其本质上是因为二维数组的使用过程中是按照行来遍历的, 其具有不返回的性质, 因此其前面的数据在后面的遍历中是不会被使用的, 因此我们可以将不用的数据使用接下来的数据来代替将其刷掉, 从而将二维数组优化为一维数组。
同理, 只要具有不返回性质的数组, 都可以用进行优化, 一维数组可以优化为变量, 三维数组可以优化为二维数组, 四维数组可以优化为三维数组, 以此类推。
二维数组优化为一维数组处理中的什么
处理的是二维数组中元素间的依赖关系, 即行与行元素之间和每一行元素之间的依赖关系, 在二维数组中, 我们经常需要复制前一行的元素并以其作为依赖进行基础运算, 因此在一维数组中我们可以保留上一行处理的元素在不被新数据刷掉的前提下就可以作为下一行的依赖。在依赖关系比较复杂的题目中, 我们可以使用双一维数组来滚动优化, 而在存在顺序依赖关系的我们甚至可以使用单一维数组通过前后顺序依赖关系实现优化, 大大节省空间。
因为其使用的多为依赖关系, 与严格位置依赖方法相同, 因此其被作为空间优化方案使用于严格位置依赖的实现的算法中。
二维数组如何优化为一维数组
二维数组在优化为一维数组需要关注依赖关系的顺序, 是从前往后, 还是从后往前, 并以此作为依据判断一维数中处理依赖关系的循环的方向。
这是一个经典的01背包问题(测试链接):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
vector<int> dp;
vector<int> costs; // 代价
vector<int> vals; // 价值
int t, n; // 总代价, 物品数量
int main()
{
cin >> t >> n;
dp = vector<int>(t + 1, 0);
costs = vector<int>(n + 1, 0);
vals = vector<int>(n + 1, 0);
for (int i = 1; i <= n; ++i)
{
cin >> costs[i] >> vals[i];
}
for (int i = 1; i <= n; ++i)
{
for (int j = t; j >= costs[i]; --j) // 依赖循环
{
dp[j] = max(dp[j], dp[j - costs[i]] + vals[i]);
}
}
cout << dp[t];
return 0;
}
上述的依赖循环, 是从后到前的依赖循环, 如果以二维进行分析的话, 我们可以发现, 每一行都是基于上一行j - costs[i]位置处理结果也就是dp[i - 1][j - costs[i]]; 因此在一维数组中, 我们保存了上一行的数据需要在不被更新前用于本行数据的修改, 因此需要判断从后完全递减完成一维数组的修改。
总结
这就是二维数组转一维数组的优化原理, 希望对你有所帮助。
