动态规划的数组压缩技巧 - 机器人走格子问题
题目是leetcode62题目原题 表示如下
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
递归版本
我们首先来想递归函数的含义 它会返回给我们一个int类型的数据 这个数据就是我们的最大路径数
我们需要给这个函数 我们当前的位置 我们需要去到的位置 整体函数如下
int _uniquePaths(int x , int y ,int m , int n)
其中 x y 代表我们当前位置的坐标 m n代表要到达位置的坐标
接下来我们想base case
因为这是一个位置限制的棋盘 所以说我们要考虑是否会越界的问题 即
if (x > m || y > n) { return 0; }
当然 当我们的走到finish位置的时候也算是结束了 会返回给我们一种路径方法 表示如下
if (x == m && y == n) { return 1; }
接下来我们就开始列举各种可能性 因为我们这里只能往下或者是往右走 所以说一共有两种可能性
我们只需要把这两种可能性所需要的路径和相加就可以了 代码表示如下
int _uniquePaths(int x , int y ,int m , int n) { // base case if (x > m || y > n) { return 0; } if (x == m && y == n) { return 1; } int p1 = _uniquePaths(x + 1 , y, m, n); int p2 = _uniquePaths(x, y + 1, m, n); return p1 + p2; }
动态规划
接下来我们开始动态规划版本的代码改写
首先我们找出一直变化的变量是什么
int _uniquePaths(int x , int y ,int m , int n)
我们发现递归中一直变化的参数其实只有两个 x 和 y
所以说我们只需要建立一张x和y的二维表就可以
x的格子一共有m个 y的格子一共有n个 所以说 x的大小可以设置为 0 ~ m-1 y的大小可以设置为0 ~ n-1
我们要知道的是 x和y可能会越界 所以说我们要设置一个pickup函数来从表中选值 如果说越界了我们直接返回0即可
int pickup_dp(int x , int y , int m , int n , vector<vector<int>>& dp) { if (x > m || y > n) { return 0; } return dp[x][y]; }
接下来我们来看base case
if (x == m && y == n) { return 1; }
也就是说 当x为最大值 y为最大值的时候 此时dp表设置为1
dp[m-1][n-1] = 1;
接下来我们开始找位置依赖关系
int p1 = _uniquePaths(x + 1 , y, m, n); int p2 = _uniquePaths(x, y + 1, m, n);
假设这个格子是表中任意一个 图中表示为黑色的格子
那么依赖的格子就是红色的
根据依赖关系 我们可以从右往左 从下往上的方式 来填写依赖关系 代码表示如下
int dp_uniquePaths(int m , int n , vector<vector<int>>& dp) { dp[m-1][n-1] = 1; for (int col = n -1 ; col >= 0 ; col--) { for (int row = m -1; row >= 0; row--) { if (row == m-1 && col == n-1) { continue; } int p1 = pickup_dp(row + 1, col, m, n, dp); int p2 = pickup_dp(row , col + 1, m, n, dp); dp[row][col] = p1 + p2; } } return dp[0][0]; }
这就是这道题目的动态规划解法
数组压缩技巧
我们可以发现的是 其实每个格子都只依赖于该列和它的右边一列 那么我们就可以使用两个列来表示整个二维表
也就是二维表转化为一维表 节省一定的空间
压缩技巧也很简单 只需要一列一列的转化就可以
代码表示如下
class Solution { public: int pickup_dp(int x , int m , vector<int>& dp) { if (x >= m || x < 0) { return 0; } return dp[x]; } int dp_uniquePaths(int m , int n ) { // col1 prev // col2 cur vector<int> col1(m , 0); vector<int> col2(m , 0); col1[m-1] = 1; for (int i = 0; i < n ; i++) { for(int j = m - 1; j >= 0; j--) { col2[j] = pickup_dp(j + 1, m, col2) + col1[j]; } for(int j = m -1 ; j >= 0 ; j--) { col1[j] = col2[j]; } } return col2[0]; } int uniquePaths(int m, int n) { return dp_uniquePaths(m , n ); } };
我们这里稍微讲解下两列的转化思路
我们设定 col1为前一列 col2为当前列
每次我们修改col2内部的值 到最后我们全部修改完毕要到下一列的时候 我们更新下col1列的所有值
