动态规划空间复杂度优化总结

使用动态规划解决问题时, 若使用从下至上的迭代法, 可能需要使用二维数组来缓存计算结果.

二维数组的空间复杂度为 $O(n^2)$, 那么需要优化缓存的大小以提高效率.

• 若使用两行的二维数组: 空间复杂度为 $O(n)$
• 若使用一维数组, 空间复杂度为 $O(n)$, 且只有两行二维数组的一半. 根据使用数据的不同, 需要适当的改变计算方向或引入变量:
  • 计算时需要左侧和正上方的数据: 从左至右
  • 计算时需要左上方和正上方的数据: 从右至左
  • 计算时需要左侧, 上方, 左上方三个数据: 从左至右, 引入变量缓存原始数据

1. 通用方式: 行数为2的二维数组

由于计算时通常只用上当前行和上一行的数据, 那么只需要两行数组即可.

此时空间复杂度为 $O(n)$

以 LCR 095. 最长公共子序列 为例, 计算部分代码如下:

dp := make([][]int, m+1)
for i := range dp {
    dp[i] = make([]int, n+1)
}

for i := range text1 {
    for j := range text2 {
        if text1[i] == text2[j] {
            dp[i+1][j+1] = dp[i][j] + 1
        } else {
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        }
    }
}
return dp[m][n]

由上可以看出, 计算时只用到了两行的数据, 将其优化成两行的二维数组:

dp := make([][]int, 2)
for i := range dp {
    dp[i] = make([]int, n+1)
}

for i := range text1 {
    for j := range text2 {
        if text1[i] == text2[j] {
            dp[(i+1)%2][j+1] = dp[i%2][j] + 1
        } else {
            dp[(i+1)%2][j+1] = max(dp[i%2][j+1], dp[(i+1)%2][j])
        }
    }
}

return dp[m%2][n]

2. 一维数组

此方式空间复杂度为 $O(n)$, 但是只有两行的二维数组的一半.

核心思想是使用一个位置存储原来二维数组的同一列的上下两行数据, 例如: dp[j] 存储 dp[i][j]和dp[i-1][j]的数据.

优化成一维数组的根据使用数据的相对位置不同, 方式可能会不一样.

2.1 计算时需要左侧和正上方的数据

若计算dp[i][j]时, 需要dp[i][j-1] 和 dp[i-1][j] 的数据, 此时无需改动计算方向, 从左至右即可.

例如: LCR 098. 不同路径, 计算部分代码如下:

dp[1][0] = 1
for i := 0; i < n; i++ {
    dp[0][i] = 1
}

// 计算
for i := 1; i < m; i++ {
    for j := 1; j < n; j++ {
        dp[i%2][j] = dp[(i-1)%2][j] + dp[i%2][j-1]
    }
}

return dp[(m-1)%2][n-1]

计算公式为dp[i][j] = dp[i-1][j] + dp[i][j-1], 若使用一维数组存储:

• 原始数据: dp[j] 为 dp[i-1][j], dp[j-1]为dp[i-1,j-1]
• 计算新数据: dp[j] = dp[j] + dp[j-1]
• 覆盖原始数据: dp[j]为 dp[i][j]
• 计算下一个数据: dp[j+1] = dp[j+1] + dp[j] 即dp[i][j+1] = dp[i-1][j+1] + dp[i][j]

可以看出覆盖原始数据不会对后续的计算造成影响, 那么从左到右的计算方向是合理的, 代码如下:

dp := make([]int, n)
for i := range dp {
    dp[i] = 1
}

for i := 1; i < m; i++ {
    for j := 1; j < n; j++ {
        dp[j] = dp[j-1] + dp[j]
    }
}

return dp[n-1]

2.2 计算时需要左上方和正上方的数据

由于不需要左侧数据, 那么可以翻转计算顺序, 从右至左计算.

此处有两种情况, 当计算dp[i][j] 时:

• 左上方数据是相邻(或者说是已知)的, dp[i-1][j-1]和dp[i-1][j] 是相邻的, 可以右两种计算方式
  • 从右至左(推荐)
  • 从左至右, 需要变量来缓存原始数据
• 左上方数据位置是未知的, 例如0-1背包问题, 计算dp[i][j]需要dp[i-1][j]和dp[i-1][j-nums[i-1]], dp[i-1][j-nums[i-1]]的位置未知无法进行缓存, 那么只能从右到左计算.

2.2.1 左上方数据是相邻(位置已知)

例如: LCR 100. 三角形最小路径和, 计算dp[i][j]需要 dp[i-1][j-1]和dp[i-1][j]

若改为一维数组:

• 原始数据: dp[j] 为 dp[i-1][j], dp[j-1]为dp[i-1,j-1]
• 计算新数据: dp[j] = dp[j] + dp[j-1]
• 覆盖原始数据: dp[j]为 dp[i][j]
• 计算下一个数据: dp[j+1] = dp[j+1] + dp[j] 即dp[i][j+1] = dp[i-1][j+1] + dp[i][j]是错误的, 此时原始的dp[j]即 dp[i-1][j]被新数据覆盖了, 影响了计算结果

可以保持计算方向, 并使用变量缓存

// 缓存
dp := make([]int, n)

// 计算
for i := 0; i < n; i++ {
    // 缓存 f(i-1,j-1)
    prev := dp[0]
    for j := 0; j <= i; j++ {
        cur := 0 // 缓存计算结果
        if j == 0 {
            cur = dp[j] + triangle[i][j]
        } else if  i == j {
            cur = prev + triangle[i][j]
        } else if  i > j { 
            cur = min(dp[j], prev) + triangle[i][j]
        }

        prev = dp[j] // 缓存之前的结果 
        dp[j] = cur  // 保存计算结果
    }
}

或者改变计算方向为从右至左

// 缓存
dp := make([]int, n)

// 计算
for i := 0; i < n; i++ {
    for j := i; j >= 0; j-- {
        if j == 0 {
            dp[j] = dp[j] + triangle[i][j]
        } else if  i == j {
            dp[j] = dp[j-1] + triangle[i][j]
        } else if  i > j { 
            dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]
        }
    }
}

2.2.2 左上方数据位置是未知的

例如: LCR 102. 目标和

此时左上方的数据dp[i-1][j-nums[i-1]]位置未知, 无法缓存, 只能从右至左进行计算.

// 缓存
dp := make([]int, t+1)
// 初始值(最小问题解)
dp[0] = 1

// 计算
for i := 1; i < n+1; i++ {
	// 从右向左计算, 避免覆盖原数据
	for j := t; j >= nums[i-1]; j-- {
		dp[j] += dp[j-nums[i-1]]
	}
}

2.3 计算时需要左侧, 上方, 左上方三个数据

此时只能够从左至右进行计算, 并且使用变量缓存左上方的数据.

例如: LCR 095. 最长公共子序列

计算dp[i][j], 需要dp[i-1][j], dp[i-1][j-1]和 dp[i][j-1]

使用一维数组, 从左至右, 缓存左上方数据

// 缓存
dp := make([]int, n+1)

// 计算
for i := range text1 {
    prev := dp[0]
    for j := range text2 {
        cur := 0 
        if text1[i] == text2[j] {
            cur = prev + 1 
        } else {
            cur = max(dp[j], dp[j+1]) 
        }
        
        prev = dp[j+1]
        dp[j+1] = cur
    }
}

Reference

1. 剑指Offer（专项突破版）
2. https://en.wikipedia.org/wiki/Dynamic_programming
3. https://leetcode.cn/studyplan/dynamic-programming/
4. 读书笔记-剑指-动态规划