🌐 中文 English
This article mainly introduces the essential logic of optimizing two-dimensional arrays into one-dimensional arrays. Test link: https://www.luogu.com.cn/problem/P1048
Introduction
When encountering problems of trading time for space (dp, knapsack problems, subarray sum accumulation, etc.), we can optimize a one-dimensional array into variables, a two-dimensional array into a one-dimensional array, a three-dimensional array into a two-dimensional array, and so on.
Among these, converting a two-dimensional array to a one-dimensional array is the most common. Therefore, this article will start from the essential algorithmic logic of optimizing a two-dimensional array into a one-dimensional array, explaining how to perform this optimization.
Why Optimize a Two-Dimensional Array into a One-Dimensional Array
Optimizing a two-dimensional array into a one-dimensional array reduces the space complexity from O(n * m) to O(m) or O(n), improving program space utilization. When data volume and values are large, this can significantly save space and disk I/O read/write time, enhancing program runtime efficiency.
Why a Two-Dimensional Array Can Be Converted into a One-Dimensional Array
Essentially, this is because during the usage of a two-dimensional array, traversal is performed row by row, and it possesses a non-returning property. This means that data from earlier rows is not used in later traversals. Therefore, we can overwrite unused data with subsequent data, thereby optimizing the two-dimensional array into a one-dimensional array.
Similarly, any array with a non-returning property can be optimized: a one-dimensional array can be optimized into variables, a three-dimensional array into a two-dimensional array, a four-dimensional array into a three-dimensional array, and so on.
What Is Handled in Optimizing a Two-Dimensional Array into a One-Dimensional Array
It deals with the dependency relationships between elements in the two-dimensional array, specifically the dependencies between rows and between elements within each row. In a two-dimensional array, we often need to copy elements from the previous row and use them as dependencies for basic operations. Therefore, in a one-dimensional array, we can retain the processed elements from the previous row, provided they are not overwritten by new data, to serve as dependencies for the next row. In problems with more complex dependency relationships, we can use dual one-dimensional arrays for rolling optimization. For problems with sequential dependencies, we can even use a single one-dimensional array to achieve optimization through front-to-back sequential dependencies, greatly saving space.
Because it primarily involves dependency relationships, similar to strict positional dependency methods, it is used as a space optimization scheme in algorithms implemented with strict positional dependencies.
How to Optimize a Two-Dimensional Array into a One-Dimensional Array
When optimizing a two-dimensional array into a one-dimensional array, attention must be paid to the order of dependency relationships—whether it is from front to back or from back to front. This determines the direction of the loop handling dependencies in the one-dimensional array.
Here is a classic 0/1 knapsack problem (Test Link):
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; // cost
vector<int> vals; // value
int t, n; // total cost, number of items
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) // dependency loop
{
dp[j] = max(dp[j], dp[j - costs[i]] + vals[i]);
}
}
cout << dp[t];
return 0;
}
The dependency loop above is a back-to-front dependency loop. If analyzed in two dimensions, we can see that each row is based on the processed result from the previous row at position j - costs[i], i.e., dp[i - 1][j - costs[i]]. Therefore, in a one-dimensional array, we preserve the data from the previous row, which must be used for modifying the current row’s data before being updated. Hence, it is necessary to determine the direction of the loop to complete the modification of the one-dimensional array from back to front.
Summary
This is the optimization principle of converting a two-dimensional array into a one-dimensional array. I hope it helps you.
