对动态规划进行空间压缩

#算法/动态规划

能够使用空间压缩技巧的动态规划都是二维 dp 问题，

• 它的状态转移方程，如果计算状态 dp[i][j] 需要的都是 dp[i][j] 相邻的状态，那么就可以使用空间压缩技巧，将二维的 dp 数组转化成一维，将空间复杂度从 O(N^2) 降低到 O(N)。

但使用空间压缩技巧对二维 dp 数组进行降维打击之后，解法代码的可读性变得非常差了，如果直接看这种解法，任何人都是一脸懵逼的。

算法的优化就是这么一个过程，先写出可读性很好的暴力递归算法，然后尝试运用动态规划技巧优化重叠子问题，最后尝试用空间压缩技巧优化空间复杂度。

更多参考： https://labuladong.online/algo/dynamic-programming/space-optimization/