二维数组压缩到一维举个例子讲解下

二维数组压缩到一维通常是处理一些线性表或序列相关的动态规划问题，其中每个子问题依赖于前一行或上一列的计算结果。例如，经典的斐波那契数列就是一个典型的例子。

原问题可能定义为：

F[i] = F[i-1] + F[i-2]

这里我们有一个二维数组 `F` 来存储所有的斐波那契数值，但实际上只需要前两个元素 `F[0]` 和 `F[1]` 就可以计算出剩余的所有值。

使用一维数组压缩，我们仅保留当前状态和前一个状态，更新过程可以这样表示：

def fibonacci(n):
    if n <= 1:
        return n
    fib = [0, 1]  # 只保留前两个元素
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    return fib[n]

# 输出第n个斐波那契数
fibonacci(10)

在这个例子中，我们用一个长度为 `n+1` 的一维数组 `fib` 替代了原来的二维数组，节省了空间。实际上，随着 `n` 的增长，这个方法的空间复杂度从 O(n^2) 减低到了 O(n)。

相关问题

二维数组压缩到一维举个复杂的例子讲解下

二维数组压缩成一维，也称为扁平化，通常是在处理数据结构或存储空间效率方面的一种技术。例如，假设我们有一个表示游戏地图的二维数组，这个地图由一个个格子组成，每个格子可以有不同的状态（如空地、障碍物或玩家位置）。原始的二维数组可能会像这样：

game_map = [
    [0, 1, 0],  # 空地，障碍物，空地
    [1, 0, 1],  # 障碍物，空地，障碍物
    [0, 1, 0]   # 空地，障碍物，空地
]

要将其压缩成一维，我们可以遍历整个数组并将每个元素添加到新的数组中，顺序不变。这里是一个复杂点的例子，我们添加额外的信息，比如每个格子的颜色：

# 每个格子现在包含状态和颜色信息
game_map_complex = [
    [0, "white", 1, "black"],  # 空地（白色），障碍物（黑色）
    [1, "black", 0, "white"],  # 障碍物（黑色），空地（白色）
    [0, "white", 1, "black"]   # 空地（白色），障碍物（黑色）
]

# 扁平化过程
flattened_map = []
for row in game_map_complex:
    flattened_map.extend(row)

flattened_map = [item for sublist in flattened_map for item in sublist]  # 或者直接使用列表推导式

print(flattened_map)  # 输出：[0, 'white', 1, 'black', 1, 'black', 0, 'white', 0, 'white', 1, 'black']

在这个例子中，一维数组`flattened_map`包含了所有原始二维数组中的元素，并保留了它们的组合顺序。