当前位置 博文首页 > 玄之不玄：动态规划中初识状态压缩（入门）
想必很多人还不知道动态规划是可以状态压缩的吧，通俗的讲就是把维数变小，一般就是把二维数组降为一维。维数变小意味着空间变小，速度还不变，不用空间换时间，这就是状态压缩的强大之处。
以leetcode64题最小路径和为例，带大家一步一步见识一下状态压缩这个小技巧
题意：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小
说明：每次只能向下或者向右移动一步
示例1
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小
函数名：
public int minPathSum(int[][] grid)
题目的最基本的状态转移方程是
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
意思是如果我们在i, j 这个位置的话从可以从两个方向推出dp[i][j]的值，题目说明了每次只能向下或者向右移动一步，如下图
完整代码如下
class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = grid[0][0];
//初始化
//从（0，0）一直向下走
for (int i = 1; i < n; i++)
dp[i][0] = dp[i - 1][0] + grid[i][0];
//从（0，0）一直向右走
for (int j = 1; j < m; j++)
dp[0][j] = dp[0][j - 1] + grid[0][j];
//状态转移
for (int i = 1; i < n; i++)
for (int j = 1; j < m; j++)
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
return dp[n - 1][m - 1];
}
}
上面的测试用例运行后的dp数组如下
上面的代码很直观吧
下面的代码是为了推出状态压缩而写的，原理和上面一样，只是上面的dp[0][0]换成下面的dp[1][1]
我这样子写不是说要这样子做，只是为了方便大家理解状态压缩而已，基本思路完全没有变
先贴出dp数组结果如下
代码如下
class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n + 1][m + 1];
//初始化
for (int i = 0; i <= n; i++)
dp[i][0] = Integer.MAX_VALUE;
dp[1][1] = grid[0][0];
//初始状态
//从（1，1）一直往右走
for (int j = 2; j <= m; j++)
dp[1][j] = dp[1][j - 1] + grid[0][j - 1];
//状态转移
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
return dp[n][m];
}
}
接下来开始进行状态压缩
把二维降为一维结果如下,采用的是直接投影的方法
投影也就是直接把dp[i][j]中i所在的那一维去掉
代码的转变过程如下
由
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]
变成
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i - 1][j - 1]
解释一下上面为什么这样子就完成了
想要求出dp[i][j]需要先求出dp[i - 1][j]和dp[i][j - 1]
我们发现二维的dp[i - 1][j]映射成了一维的dp[j],dp[i][j - 1]映射成了dp[j - 1]
所需要的信息都能直接用一维来表示
哪怕dp[j]被覆盖了也没事，原因看下图
所以
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i - 1][j - 1]
完整代码如下：
class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length;
int m = grid[0].length;
int[] dp = new int[m + 1];
//初始化
dp[0] = Integer.MAX_VALUE;
dp[1] = grid[0][0];
//从（1，1）一直向右走 真的只是把上面的代码中dp[i][j]的i那一维去掉
for (int j = 2; j <= m; j++)
dp[j] = dp[j - 1] + grid[0][j - 1];
//这里也是直接去掉i中的那一维
for (int i = 2; i <= n; i++)
for (int j = 1; j <= m; j++)
dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i - 1][j - 1];
return dp[m];
}
}
这题到这里也就结束了
这题的状态压缩之所以简单是因为没有多个元素映射到同一个位置
如果如下图所示的话
一旦映射就会有两个状态映射到同一个位置，这里提示一下，此时也很简单，只需要定义一个变量，来存储那两个映射到同一个位置的两个变量中的其中一个变量就行了
后面我有空也会写一下两个状态映射到同一位置的这种情况
这里只是大概帮助你们入一下门。以后你看到有两个状态映射到同一位置的状态压缩的代码时，也能很轻松的读懂
这或许也是为什么面试官那么看重计算机基础，不就是因为计算机基础是一切的基石，计算机基础稳了，上手其他那不是手到擒来
图片目前做的不是很美观，以后会慢慢优化。
如果觉得有收获，不妨花个几秒钟点个赞，欢迎关注我的公众号玩编程地码农，目前会不断写与java、数据结构与算法和计算机基础相关的知识等。
