动态规划的空间压缩技巧（降低空间复杂度）

空间规划的灵魂在于传达生活态度 #生活乐趣# #生活艺术# #生活美学设计# #艺术空间规划#

空间压缩 可以理解为一种投机取巧的办法去优化某些动态规划问题的空间复杂度。

本文的优化方式，通过观察状态转移方程之间的依赖关系，从而减少dp数组的维度。能够使用状态压缩的都是二维dp数组问题，如果计算状态dp[i][j]需要的都是dp[i][j]相邻的状态，那么就可以使用状态压缩将二维dp数组压缩到一维。

LeetCode516 最长回文子序列 动态规划求解

 

int longestPalindromeSubseq(string s) {

int row = s.length(), column = s.length();

int dp[row][column];

​

for (int i = 1; i < row; i++) {

for (int j = i - 1; j >= 0; j--) {

dp[i][j] = 0;

}

}

for (int i = 0; i < row; i++) {

dp[i][i] = 1;

}

​

for (int i = row - 2; i >= 0; i--) {

for (int j = i + 1; j < column; j++) {

if (s[i] == s[j]) {

dp[i][j] = dp[i + 1][j - 1] + 2;

} else {

dp[i][j] = std::max(dp[i + 1][j], dp[i][j - 1]);

}

}

}

return dp[0][column - 1];

}

本文只探讨如何使用 空间压缩 这一技巧，并不着重讲解 如何推导状态转移方程 ，技巧都是通用的，在应对二维dp数组时，可以考虑利用空间压缩技巧降低空间复杂度

对此题的空间压缩剖析

我们对于 dp[i][j] 的更新，其实只依赖 dp[i+1][j-1], dp[i+1][j], dp[i][j-1]这三个状态，如下图

这就叫相邻状态，计算dp[i][j] 状态，只需要通过计算 dp[i+1][j-1], dp[i+1][j], dp[i][j-1]这三个状态即可，根本就不需要那么大的二维dp表，空间压缩 的核心思路是 将二维dp数组投影为一维。

投影时会产生一个问题：图中 dp[i][j-1] 和 dp[i+1][j-1] 这两个状态处在同一列，而一维数组中只能容下一个，那么他俩投影到一维必然有一个会被另一个覆盖掉，我们还怎么计算 dp[i][j] 呢？

这是空间压缩的重点与难点。我们仍以 最长回文子序列 为例，它的状态转移方程主要逻辑是以下代码：

for (int i = row - 2; i >= 0; i--) {

for (int j = i + 1; j < column; j++) {

if (s[i] == s[j]) {

dp[i][j] = dp[i + 1][j - 1] + 2;

} else {

dp[i][j] = std::max(dp[i + 1][j], dp[i][j - 1]);

}

}

}

由上图可知，投影 就是把多行变成一行，所以想把 二维dp 压缩成 一维dp ,在一般情况下，就是去除i 这个维度，只留下j 。压缩后的一维dp 就是原来 二维dp 的dp[i][...] 那一行。

现在我们先无脑去除i 这个维度，把dp数组变成一维,得到以下代码：

for (int i = row - 2; i >= 0; i--) {

for (int j = i + 1; j < column; j++) {

if (s[i] == s[j]) {

dp[j] = dp[j - 1] + 2;

} else {

dp[j] = std::max(dp[j], dp[j - 1]);

}

}

}

根据之前的分析，dp[i][j] 的值由 dp[i+1][j-1], dp[i][j-1], dp[i+1][j] 计算出来，但是压缩之后的dp[j] 只能表示 dp[i][...] 这一行，dp[i+1][j-1], dp[i+1][j] 该如何表示呢？

在代码注释的位置，需要进行状态转移，更新dp[j]，我们需要思考下面两个问题：

在更新之前，dp[j]代表什么？dp[j]对应二维dp 里的什么位置？

dp[j-1]对应二维dp 里的什么位置？

观察代码很容易发现，dp[j] 对应上一层外循环里面的dp[i+1][j]，dp[j-1] 对应上一层内循环里的dp[i][j-1]。现在只剩下dp[i+1][j-1] 的值未知，但我们知道，dp[i+1][j-1] 对应上一层外循环里对应j的内循环的上一层内循环，简而言之就是dp[j]的上一层内循环，所以我们在覆盖dp[j]时，需要新建一个临时变量来保存即将被覆盖的原来的dp[j],这样在下一层内循环中，pre就代表dp[i+1][j-1]，代码如下：

for (int i = row - 2; i >= 0; i--) {

int pre = 0;

for (int j = i + 1; j < column; j++) {

int temp = dp[j];

if (s[i] == s[j]) {

dp[j] = pre + 2;

} else {

dp[j] = std::max(dp[j], dp[j - 1]);

}

pre = temp;

}

}

现在我们已经成功 二维dp 进行了降维打击，但是注意，还需要注意base case：

先回顾 二维dp 的base case:

 int dp[n][n] = {{0}};  ​  for(int i = 0;i<n;i++){ //单个字符也可以构成回文子串      dp[i][i] = 1;  }

空间压缩就是投影，我们看下图，一维dp 的base case显而易见：

很显然，一维数组的dp[i]全为1：

 int dp[n] = {1};//第一个元素初始化为1，剩下的会被初始化为和第一个元素相同的值

我们可以得出最终代码：

 

int longestPalindromeSubseq(string s) {

int n = s.length();

int dp[n];

memset(dp, 1, sizeof(dp));

for (int i = n - 2; i >= 0; i--) {

int pre = 0;

for (int j = i + 1; j < n; j++) {

int temp = dp[j];

if (s[i] == s[j])

dp[j] = pre + 2;

else

dp[j] = max(dp[j], dp[j - 1]);

pre = temp;

}

}

return dp[n - 1];

}

总结

空间压缩再厉害，终究是建立在常规动态规划的思路之上的。在进行空间压缩之后，代码的可读性变得极差，如果直接看这种解法，大多数人会一脸懵逼，算法的优化就是这么一个过程，先写出可读性很好的暴力递归解法，然后尝试利用动态规划技巧优化重叠子问题（降低时间复杂度），再尝试利用空间压缩技巧优化空间复杂度。

LeetCode63 不同路径

未进行空间压缩的代码：

int uniquePathsWithObstacles(vector <vector<int>> &obstacleGrid) {

int row = obstacleGrid.size();

int column = obstacleGrid[0].size();

​

​

std::vector<vector<int>> dp(row,std::vector<int>(column,0));

​

if (obstacleGrid[0][0] == 1) return 0;

dp[0][0] = 1;

for (int j = 1; j < column; j++) {

if (obstacleGrid[0][j] == 1) dp[0][j] = 0;

else {

dp[0][j] = dp[0][j - 1];

}

}

for (int i = 1; i < row; i++) {

if (obstacleGrid[i][0] == 1) dp[i][0] = 0;

else {

dp[i][0] = dp[i - 1][0];

}

}

​

for (int i = 1; i < row; i++) {

for (int j = 1; j < column; j++) {

if (obstacleGrid[i][j] == 1) dp[i][j] = 0;

else {

dp[i][j] = dp[i][j - 1] + dp[i - 1][j];

}

}

}

​

return dp[row - 1][column - 1];

}

简单分析：

dp[j]更新之前，dp[j]表示什么？

dp[j-1]又表示什么？

可以发现，投影之后的dp[j] 表示上一层外循环的dp[i-1][j]，dp[j-1] 表示上一层内循环的dp[i][j-1],恰好，dp[i][j]只取决于dp[i-1][j],dp[i][j-1],所以投影之后迭代框架很容易得知,为

 for (int i = 1; i < row; i++) {      for (int j = 1; j < column; j++) {          if (obstacleGrid[i][j] == 1) dp[j] = 0;          else {              dp[j] = dp[j-1] + dp[j];         }     }  }

经过状态转移之后, dp[column-1] 就是最终结果。

接下来分析投影之后的base case：

此处与之前例题的base case分析略有不同，我们注意到，如果我们只将二维dp 的第一行作为base case，那么直接投影到一维dp 即可，刚好可以一一对应上，但是，我们之前的二维dp 中将第一行和第一列作为base case，我们想想，第一列投影到 一维dp 上会发生什么，n个数最后只能取一个数！！！ ，这种投影不是好的投影方法，所以我们在一维dp 中不投影第一列。只要简单改一下循环代码就可以代替二维dp第一列的base case功能。如下：

 int dp[column];  //base case  for(int j=0;j<column;j++){      dp[j] = (obstacleGrid[0][j]==1 ? 0,dp[j-1]);  }  ​  for (int i = 1; i < row; i++) {      //内循环改为从第一列开始      for (int j = 0; j < column; j++) {          if (obstacleGrid[i][j] == 1) dp[j] = 0;          //第一列的状态转移和其他列，单独处理即可          else if(j == 0){              dp[j] = dp[j];         }          else {              dp[j] = dp[j-1] + dp[j];         }     }  }

最终得出，空间压缩后的代码：

int uniquePathsWithObstacles(vector <vector<int>> &obstacleGrid) {

int row = obstacleGrid.size();

int column = obstacleGrid[0].size();

​

​

int dp[column];

if (obstacleGrid[0][0] == 1) return 0;

else dp[0] = 1;

for (int j = 1; j < column; j++) {

dp[j] = (obstacleGrid[0][j] == 1 ? 0 : dp[j - 1]);

}

​

for (int i = 1; i < row; i++) {

for (int j = 0; j < column; j++) {

if (obstacleGrid[i][j] == 1) dp[j] = 0;

else if (j == 0) {

dp[j] = dp[j];

} else {

dp[j] = dp[j - 1] + dp[j];

}

}

}

​

return dp[column - 1];

}

网址：动态规划的空间压缩技巧（降低空间复杂度） https://www.yuejiaxmz.com/news/view/566643

相关内容

动态规划的时间复杂度优化
时间复杂度和空间复杂度详解
动态规划优化技巧.doc
[上海波涛装饰]装修如何做好空间优化？家装空间规划技巧
动态规划算法的优化技巧（转贴）
算法优化的艺术：降低时间复杂度与提升算法效率的实战技巧
二维动态规划空间优化
真空压缩袋材质区别 真空压缩袋挑选技巧
算法小技巧：空间换时间，时间换空间？
如何收纳和利用小厨房的空间？这种空间规划的技巧有哪些？

随便看看