共计 3781 个字符,预计需要花费 10 分钟才能阅读完成。
咱们号之前写过十几篇动静布局文章,能够说动静布局技巧对于算法效率的晋升十分可观,一般来说都能把指数级和阶乘级工夫复杂度的算法优化成 O(N^2),堪称算法界的二向箔,把各路魑魅魍魉通通打成二次元。
然而,动静布局自身也是能够进行阶段性优化的,比如说咱们常据说的「状态压缩」技巧,就可能把很多动静布局解法的空间复杂度进一步升高,由 O(N^2) 升高到 O(N),
可能应用状态压缩技巧的动静布局都是二维 dp
问题,你看它的状态转移方程,如果计算状态 dp[i][j]
须要的都是 dp[i][j]
相邻的状态,那么就能够应用状态压缩技巧,将二维的 dp
数组转化成一维,将空间复杂度从 O(N^2) 升高到 O(N)。
什么叫「和 dp[i][j]
相邻的状态」呢,比方前文 最长回文子序列 中,最终的代码如下:
int longestPalindromeSubseq(string s) {int n = s.size();
// dp 数组全副初始化为 0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
dp[i][i] = 1;
// 反着遍历保障正确的状态转移
for (int i = n - 2; i >= 0; i--) {for (int j = i + 1; j < n; j++) {
// 状态转移方程
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
// 整个 s 的最长回文子串长度
return dp[0][n - 1];
}
PS:咱们本文不探讨如何推状态转移方程,只探讨对二维 DP 问题进行状态压缩的技巧。技巧都是通用的,所以如果你没看过前文,不明确这段代码的逻辑也不妨,齐全不会妨碍你学会状态压缩。
PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全副公布在 labuladong 的算法小抄,继续更新 。倡议珍藏, 依照我的文章程序刷题,把握各种算法套路后投再入题海就蛟龙得水了。
你看咱们对 dp[i][j]
的更新,其实只依赖于 dp[i+1][j-1], dp[i][j-1], dp[i+1][j]
这三个状态:
这就叫和 dp[i][j]
相邻,反正你计算 dp[i][j]
只须要这三个相邻状态,其实基本不须要那么大一个二维的 dp table 对不对?状态压缩的外围思路就是,将二维数组「投影」到一维数组:
思路很直观,然而也有一个显著的问题,图中 dp[i][j-1]
和 dp[i+1][j-1]
这两个状态处在同一列,而一维数组中只能容下一个,那么当我计算 dp[i][j]
时,他俩必然有一个会被另一个笼罩掉,怎么办?
这就是状态压缩的难点,上面就来剖析解决这个问题,还是拿「最长回文子序列」问题间隔,它的状态转移方程次要逻辑就是如下这段代码:
for (int i = n - 2; i >= 0; i--) {for (int j = i + 1; j < n; j++) {
// 状态转移方程
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j - 1] + 2;
else
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
想把二维 dp
数组压缩成一维,一般来说是把第一个维度,也就是 i
这个维度去掉,只剩下 j
这个维度。压缩后的一维 dp
数组就是之前二维 dp
数组的 dp[i][..]
那一行。
咱们先将上述代码进行革新,间接无脑去掉 i
这个维度,把 dp
数组变成一维:
for (int i = n - 2; i >= 0; i--) {for (int j = i + 1; j < n; j++) {
// 在这里,一维 dp 数组中的数是什么?if (s[i] == s[j])
dp[j] = dp[j - 1] + 2;
else
dp[j] = max(dp[j], dp[j - 1]);
}
}
上述代码的一维 dp
数组只能示意二维 dp
数组的一行 dp[i][..]
,那我怎么能力失去 dp[i+1][j-1], dp[i][j-1], dp[i+1][j]
这几个必要的的值,进行状态转移呢?
在代码中正文的地位,将要进行状态转移,更新 dp[j]
,那么咱们要来思考两个问题:
1、在对 dp[j]
赋新值之前,dp[j]
对应着二维 dp
数组中的什么地位?
2、dp[j-1]
对应着二维 dp
数组中的什么地位?
对于问题 1,在对 dp[j]
赋新值之前,dp[j]
的值就是外层 for 循环上一次迭代算进去的值,也就是对应二维 dp
数组中 dp[i+1][j]
的地位。
对于问题 2,dp[j-1]
的值就是内层 for 循环上一次迭代算进去的值,也就是对应二维 dp
数组中 dp[i][j-1]
的地位。
那么问题曾经解决了一大半了,只剩下二维 dp
数组中的 dp[i+1][j-1]
这个状态咱们不能间接从一维 dp
数组中失去:
for (int i = n - 2; i >= 0; i--) {for (int j = i + 1; j < n; j++) {if (s[i] == s[j])
// dp[i][j] = dp[i+1][j-1] + 2;
dp[j] = ?? + 2;
else
// dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
dp[j] = max(dp[j], dp[j - 1]);
}
}
因为 for 循环遍历 i
和 j
的程序为从左向右,从下向上,所以能够发现,在更新一维 dp
数组的时候,dp[i+1][j-1]
会被 dp[i][j-1]
笼罩掉,图中标出了这四个地位被遍历到的秩序:
那么如果咱们想得到 dp[i+1][j-1]
,就必须在它被笼罩之前用一个长期变量 temp
把它存起来,并把这个变量的值保留到计算 dp[i][j]
的时候。为了达到这个目标,联合上图,咱们能够这样写代码:
for (int i = n - 2; i >= 0; i--) {// 存储 dp[i+1][j-1] 的变量
int pre = 0;
for (int j = i + 1; j < n; j++) {int temp = dp[j];
if (s[i] == s[j])
// dp[i][j] = dp[i+1][j-1] + 2;
dp[j] = pre + 2;
else
dp[j] = max(dp[j], dp[j - 1]);
// 到下一轮循环,pre 就是 dp[i+1][j-1] 了
pre = temp;
}
}
别小看这段代码,这是一维 dp
最精妙的中央,会者不难,难者不会。为了清晰起见,我用具体的数值来拆解这个逻辑:
假如当初 i = 5, j = 7
且 s[5] == s[7]
,那么当初会进入上面这个逻辑对吧:
if (s[5] == s[7])
// dp[5][7] = dp[i+1][j-1] + 2;
dp[7] = pre + 2;
我问你这个 pre
变量是什么?是内层 for 循环上一次迭代的 temp
值。
PS:我认真写了 100 多篇原创,手把手刷 200 道力扣题目,全副公布在 labuladong 的算法小抄,继续更新 。倡议珍藏, 依照我的文章程序刷题,把握各种算法套路后投再入题海就蛟龙得水了。
那我再问你内层 for 循环上一次迭代的 temp
值是什么?是 dp[j-1]
也就是 dp[6]
,但这是外层 for 循环上一次迭代对应的 dp[6]
,也就是二维 dp
数组中的 dp[i+1][6] = dp[6][6]
。
也就是说,pre
变量就是 dp[i+1][j-1] = dp[6][6]
,也就是咱们想要的后果。
那么当初咱们胜利对状态转移方程进行了降维打击,算是最硬的的骨头啃掉了,但留神到咱们还有 base case 要解决呀:
// dp 数组全副初始化为 0
vector<vector<int>> dp(n, vector<int>(n, 0));
// base case
for (int i = 0; i < n; i++)
dp[i][i] = 1;
如何把 base case 也打成一维呢?很简略,记住状态压缩就是投影,咱们把 base case 投影到一维看看:
二维 dp
数组中的 base case 全都落入了一维 dp
数组,不存在抵触和笼罩,所以说咱们间接这样写代码就行了:
// 一维 dp 数组全副初始化为 1
vector<int> dp(n, 1);
至此,咱们把 base case 和状态转移方程都进行了降维,实际上曾经写出残缺代码了:
int longestPalindromeSubseq(string s) {int n = s.size();
// base case:一维 dp 数组全副初始化为 0
vector<int> dp(n, 1);
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];
}
本文就完结了,不过状态压缩技巧再牛逼,也是基于惯例动静布局思路之上的。
你也看到了,应用状态压缩技巧对二维 dp
数组进行降维打击之后,解法代码的可读性变得十分差了,如果间接看这种解法,任何人都是一脸懵逼的。算法的优化就是这么一个过程,先写出可读性很好的暴力递归算法,而后尝试使用动静布局技巧优化重叠子问题,最初尝试用状态压缩技巧优化空间复杂度。
也就是说,你最起码可能纯熟使用咱们前文 动静布局框架套路详解 的套路找出状态转移方程,写出一个正确的动静布局解法,而后才有可能察看状态转移的状况,剖析是否可能应用状态压缩技巧来优化。
心愿读者可能操之过急,层层递进,对于这种比拟极限的优化,不做也罢。毕竟套路存于心,走遍天下都不怕!