[LeetCode] Unique Paths && Unique Paths II && Minimum Path Sum (动态规划之 Matrix DP )

Unique Paths

https://oj.leetcode.com/problems/unique-paths/

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

[LeetCode] Unique Paths && Unique Paths II && Minimum Path Sum (动态规划之 Matrix DP )

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

我的思路

我个人通常喜欢将此类问题,叫做 Matrix DP 问题,这道题很显然需要使用动态规划来做,一般做此类 Matrix DP 问题,通常需要注意以下几点:

state: f[x][y] 表示我从起点走到坐标x,y……
function: 研究最后一步怎么走
intialize: 起点
answer: 终点

先来看 state ,可以这样定义,f[x][y] 表示从起点 (0,0) 出发,到达 (x,y) 的 unique paths

再来看看怎么找状态转移方程,不难发现,从起点出发到达点 (x,y) 的 unique paths 实际上等于从起点出发到达该点左边一点(也就是(x,y-1))的 unique paths 加上从起点出发到达该点上面一点(也就是(x-1, y))的 unique paths 后的和。

显然该 f 矩阵的初始化是将最左边的一列和最上面的一行置为 1 ,因为由起点出发无论往下走还是往右走,该列或者该行上的每一点的 unique paths 均为1,注意即使 start 位置等于 finish 位置(也就是只有一个点),其 unique paths 也为1(自己走向自己算 1 )。

下面是我在 LeetCode 上 AC 的代码:

/**
* Zhou J
*/ class Solution
{
public:
int uniquePaths(int m, int n)
{
if (m == 0 || n == 0) {
return 0;
} int sum[m][n]; for (int i = 0; i < m; i++) {
sum[i][0] = 1;
} for (int i = 0; i < n; i++) {
sum[0][i] = 1;
} for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
}
} return sum[m - 1][n - 1];
}
};

如果你们理解了上面这一题,可以接着来看下面的 follow question。

Follow Question

Unique Paths II

https://oj.leetcode.com/problems/unique-paths-ii/

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

下面是我 AC 的代码:

/**
* Zhou J
*/ class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if (obstacleGrid.size() == 0)
{
return 0;
} int numOfRows = obstacleGrid.size();
int numOfCols = obstacleGrid[0].size();
vector<vector<int>> sum(obstacleGrid); // initialize the left column
for (size_t ix = 0; ix != numOfRows; ++ix)
{
if (obstacleGrid[ix][0] == 0)
{
sum[ix][0] = 1;
}
else
{
for (size_t newIx = ix; newIx != numOfRows; ++newIx)
{
sum[newIx][0] = 0;
}
break; } // initialize the top row
for (size_t ix = 0; ix != numOfCols; ++ix)
{
if (obstacleGrid[0][ix] == 0)
{
sum[0][ix] = 1;
}
else
{
for (size_t newIx = ix; newIx != numOfCols; ++newIx)
{
sum[0][newIx] = 0;
}
break;
}
} // switch the state
for (size_t i = 1; i != numOfRows; ++i)
{
for (size_t j = 1; j != numOfCols; ++j)
{
if (obstacleGrid[i][j] == 0)
{
sum[i][j] = sum[i-1][j] + sum[i][j-1];
}
else
{
sum[i][j] = 0;
} }
} // return the answer
return sum[numOfRows - 1][numOfCols - 1];
}
};

这倒题目相对上一题,有这样两个注意点:

1. 在初始化行和列的时候,如果有某一个点为障碍物,那么不仅仅该位置所对应的 sum 将置为0,而是其接下来的每一个位置所对应的 sum 都要置为0,这很好理解,一行或一列都属于直线,其中只要有一个障碍物,那么这一整条线路就废掉了。

2. 状态转移的过程中,如果遇到障碍物,改点应该直接返回 0 。

Minimum Path Sum

我们最后再来看一道 Matrix DP 相关的问题,如下:

Minimum Path Sum

https://oj.leetcode.com/problems/minimum-path-sum/

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

此题,实际上和上面两题属于一个套路,只不过此处的状态矩阵 sum 存放的是最短路径和。从起点出发到达某个位置的最短路径和,一定是从起点出发到达该位置左边或者上面一点的最短路径(两者取较小的)加上该点自身的路径。

state: f[x][y]从起点走到x,y的最短路径
function: f[x][y] = min(f[x-1][y], f[x][y-1]) + cost[x][y]
intialize: f[0][0] = cost[0][0]
             f[i][0] = sum(0,0 -> i,0)
             f[0][i] = sum(0,0 -> 0,i)
answer: f[n-1][m-1]

下面是 AC 的代码:

/**
* Zhou J
*/
class Solution {
public:
int minPathSum(vector<vector<int> > &grid)
{
if (grid.size() == 0)
{
return 0;
} int numOfRows = grid.size();
int numOfCols = grid[0].size();
vector<vector<int>> sum(grid); sum[0][0] = grid[0][0]; // initialize the left column
for (size_t ix = 1; ix != numOfRows; ++ix)
{
sum[ix][0] = sum[ix - 1][0] + grid[ix][0];
} // initialize the top row
for (size_t ix = 1; ix != numOfCols; ++ix)
{
sum[0][ix] = sum[0][ix - 1] + grid[0][ix];
} // switch the state
for (size_t i = 1; i != numOfRows; ++i)
{
for (size_t j = 1; j != numOfCols; ++j)
{
sum[i][j] = min(sum[i][j - 1], sum[i - 1][j]) + grid[i][j];
}
} // return the minimum path sum
return sum[numOfRows - 1][numOfCols - 1]; }
};

刷题心得

LeetCode 是一个非常好的平台,我们在上面做题时,一定要自己先思考,不要急于去 google 答案,如果你的代码 AC 不过,LeetCode 是会把过不了的 TestCase 显示给你的,根据这些提示,我们一步步修正答案,往往会得到很好的锻炼。

个人以为 Matrix DP 一类的动态规划问题通常是最简单的,对于此类题目,initialize 这一步往往是初始化起点对应的行和列。在之后的文章中,我也会针对北美一些面试题中涉及到的动态规划问题做进一步分析。

笔者目前还在国内读硕士,但是前些阶段和一些目前仍然在国内工作,但是日后想去湾区工作的朋友们交流,有一个问题是如果经常跳槽的话,会不会影响北美的面试?答案是会有影响的。我咨询了一个Facebook 的面试官,他的意思是做 intern 经常换工作是无所谓的,但是 fulltime 经常换的话,影响还是很大的。打个比方来说,intern 就相当于女朋友,这个社会现在还是允许我们经常换女朋友的(是有点贱贱嗒),但是 fulltime 就相当于 wife ,你总不能老离婚吧?!

PS:我是有多想去湾区工作啊,求内推~!!

上一篇:Ractive 的 认识


下一篇:Integer.parseInt不同jdk源码解析