https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/edit#
3. 机器人左上到右上(高频 9次)
LC类似题目: LC 62 Unique Paths 和 LC 63 Unique Paths II
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
Rules：
1. 从左上角走到右上角
2. 机器人只能走右上，右和右下;j
1. 从左上角走到右上角
2. 机器人只能走右上，右和右下;j
思路:
- 按照列dp, dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + dp[i + 1][j - 1]， 注意i-1，i+1需要存在
followup1: 优化空间复杂度至 O(n)
思路：只保留上一列的空间，用两个数组滚动dp
参考代码
provider: null
public int uniquePaths(int rows, int cols) {
int[] dp = new int[rows];
int[] tmp = new int[rows];
dp[0] = 1;
for(int j = 1 ; j < cols ; j++) {
for(int i = 0 ; i < rows ; i++) {
int val1 = i - 1 >= 0 ? dp[i - 1] : 0;
int val2 = dp[i];
int val3 = i + 1 < rows ? dp[i + 1] : 0;
tmp[i] = val1 + val2 + val3;
}
System.arraycopy(tmp, 0, dp, 0, tmp.length);
}
return dp[0];
}
C++ version:
(Provider: Anonym)
int uniquePath(const vector<vector<int>>& grid) {
if(grid.empty() or grid[0].empty()) return 0;
int rows = grid.size(), cols = grid[0].size();
vector<int> pre(rows, 0), cur(rows, 0);
pre[0] = 1;
for(int j = 1 ; j < cols; j++) {//roll on by column
for(int i = 0; i < rows; i++) {
//simply means: cur[i]=pre[i]+pre[i-1]+pre[i+1]
cur[i] = pre[i] + (i-1>=0? pre[i-1] : 0) + (i+1<rows? pre[i+1]: 0) ;
}
cur.swap(pre);
}
return pre[0];
}
滚动数组用位操作写起来会比较清晰，而且可以避免额外的copy
int uniquePath(const vector<vector<int>>& grid) {
if(grid.empty() || grid[0].empty()) return 0;
int rows = grid.size(), cols = grid[0].size();
vector<vector<int>> dp(2, vector<int>(rows, 0));
pre[0][0] = 1;//(ze yang)应该是dp吧，不过改了还是不对
int e = 1;
for(int j = 1 ; j < cols; j++, e ^= 1) {//roll on by column
for(int i = 0; i < rows; i++) {
dp[e][i] = dp[e ^ 1][i] + (i-1>=0? dp[e ^ 1][i - 1] : 0) + (i+1<rows? dp[e ^ 1][i + 1]: 0) ;
}
}
return dp[e ^ 1][0];
}
followup2: 给定矩形里的三个点，判断是否存在遍历这三个点的路径
思路：
假设三个点坐标为(x1, y1) (x2, y2) (x3, y3)
1：从(0,0)出发，如果后一个点在前一个点展开的扇形区域内，则可以被达到
2：先对三个点按照纵坐标y排序，如果一个y上有一个以上的点，则返回false
请问这是是不是应该是如果x上有一样的点返回false啊，方向如果是→ ↗ ↘的话，x应该是单调增的 y可以不是单调吧，还是我理解的题目不太对，感谢 （Editor: 这里的Y是列坐标，即j，不是坐标系中的纵坐标）
(这个没有看太懂从（0 0）怎么走？ 是不是不只是向右 和 向下)
（Editor：这个只是follow up，题目还是原题，只能往右边，右上和右下走）
3：对于(xi, yi)，得到前一个点在该列的可达范围
len = yi - y(i-1)
upper = x(i-1) - len
lower = x(i-1) + len
如果[xi]在这个范围内 (lower <= xi <= upper)，则可达
参考代码
provider: null
public boolean canReach(int[][] points) {
List<int[]> list = new ArrayList<>();
list.add(new int[] {0, 0});
for(int[] point : points) list.add(point);
Collections.sort(list, (a, b) -> {
return a[1] - b[1];
});
for(int i = 1 ; i < list.size() ; i++) {
int[] curr = list.get(i);
int[] prev = list.get(i-1);
if(curr[1] == prev[1]) return false;// 此处的判断不够严谨；还有一种情况是，两个点在同一列上，但这两个点其实是同一个点，则我们不应该直接zhi'jiefalse
int len = curr[1] - prev[1];
int upper = prev[0] - len;
int lower = prev[0] + len;
if(curr[0] <= lower && curr[0] >= upper) continue;
else return false;
}
return true;
}
List<int[]> list = new ArrayList<>();
list.add(new int[] {0, 0});
for(int[] point : points) list.add(point);
Collections.sort(list, (a, b) -> {
return a[1] - b[1];
});
for(int i = 1 ; i < list.size() ; i++) {
int[] curr = list.get(i);
int[] prev = list.get(i-1);
if(curr[1] == prev[1]) return false;// 此处的判断不够严谨；还有一种情况是，两个点在同一列上，但这两个点其实是同一个点，则我们不应该直接zhi'jiefalse
int len = curr[1] - prev[1];
int upper = prev[0] - len;
int lower = prev[0] + len;
if(curr[0] <= lower && curr[0] >= upper) continue;
else return false;
}
return true;
}
Questions
个人认为，上述思路存在逻辑问题。
假设p1, p2两个点，如果p1可以到p2，可以推出p2在p1的后置扇形区域。但是，p2在p1的后置扇形区域，并不能推出说
followup3: 给定矩形里的三个点，找到遍历这三个点的所有路径数量
思路：
1：还是按照follow up 1的思路用滚动数组dp，但是如果当前列有需要到达的点时，只对该点进行dp，其他格子全部置零，表示我们只care这一列上经过目标点的路径
2：如果一列上有多个需要达到的点，直接返回0；
参考代码
provider: null
public int uniquePaths(int rows, int cols, int[][] points) {
int[] dp = new int[rows];
int[] tmp = new int[rows];
Map<Integer, Integer> map = new HashMap<>();
for(int[] point : points) {
if(map.containsKey(point[1])) {
return 0;
} else {
map.put(point[1], point[0]);
}
}
int res = 0;
dp[0] = 1;
for(int j = 1 ; j < cols ; j++) {
for(int i = 0 ; i < rows ; i++) {
int val1 = i - 1 >= 0 ? dp[i - 1] : 0;
int val2 = dp[i];
int val3 = i + 1 < rows ? dp[i + 1] : 0;
tmp[i] = val1 + val2 + val3;
}
System.arraycopy(tmp, 0, dp, 0, tmp.length);
if(map.containsKey(j)) {
int row = map.get(j);
for(int i = 0 ; i < rows ; i++) {
if(i != row) dp[i] = 0;
else res = dp[i];
}
}
}
return res;
}
followup4: 给定一个下界
(x == H)，找到能经过给定下界的所有从左上到右上的路径数量 (x >= H)
思路：
1：先dp一遍，得到所有到右上的路径数量
2：然后在 0<=x<=H, 0<=y<=cols 这个小矩形中再DP一遍得到不经过下界的所有路径数量
3：两个结果相减得到最终路径数量
Code
重用follow up 1的代码
public int uniquePaths(int rows, int cols, int H) {
return uniquePaths(rows, cols) - uniquePaths(H, cols);
}
followup5: 起点和终点改成从左上到左下，每一步只能 ↓↘↙，求所有可能的路径数量
参考代码：按照 行 dp，其他地方不变
Provider: null
public int uniquePaths(int rows, int cols) {
int[] dp = new int[cols];
int[] tmp = new int[cols];
dp[0] = 1;
for(int i = 1 ; i < rows ; i++) {
for(int j = 0 ; j < cols ; j++) {
int val1 = j - 1 >= 0 ? dp[j - 1] : 0;
int val2 = dp[j];
int val3 = j + 1 < cols ? dp[j + 1] : 0;
tmp[i] = val1 + val2 + val3;
}
System.arraycopy(tmp, 0, dp, 0, tmp.length);
}
return dp[0];
}
补充一个该题目变种：
Given a N*N matrix with random amount of money in each cell, you start from top-left, and can only move from left to right, or top to bottom one step at a time until you hit the bottom right cell. Find the path with max amount of money on its way.
Sample data:
start
|
v
5, 15,20, ...
10, 15, 5, ...
30, 5, 5, ...
…
^end here.
Sample data:
start
|
v
5, 15,20, ...
10, 15, 5, ...
30, 5, 5, ...
…
^end here.
思路：LC 64 最小路径和，思路差不多，只是求和变成求相加后的最大值
Follow up 1：要求重建从end 到 start的路径
思路：用另一个额外数组记录每一步选择的parent，dp结束后，从end依次访问它的parent重建路径
Follow up 2: 现在要求空间复杂度为O（1），dp且重建路径
空间复杂度不算返回路径时需要的空间
思路：直接修改原数组，而且带上符号，负号表示从当前cell的左边过来，正号表示从当前cell的上边过来，dp结束后从end 依次访问它的parent重建路径
数组全是零(或者左上角一块是零)的话就没有办法通过正负号判断来的方向了吧，这样在重构path的时候可能会index out of bound，觉得还是check左边和右边哪个更大就是从那边来的更好，然后注意第一行和第一列的特殊情况，这样不会出问题
（这个方法是面试官给的hint提示的，原数组应该都是正整数。如果全是0，用正负号表示也可以特殊处理一下第一行和第一列的情况即可，即遇到i为0时候总是往左走，j为0的时候总是往上走。）
参考代码
Provider: null
public List<List<Integer>> maxMoney(int[][] moneys) {
// assume: moneys is not null, width and length are equal
int n = moneys.length;
if (n == 0)
return new ArrayList<>();
// base case
for (int j = 1; j < n; j++) {
moneys[0][j] = -(Math.abs(moneys[0][j-1]) + moneys[0][j]);
}
for (int i = 1 ; i < n ; i++) {
moneys[i][0] = moneys[i-1][0] + moneys[i][0];
}
for(int i = 1; i < n ; i++) {
for(int j = 1; j < n ; j++) {
int top = Math.abs(moneys[i-1][j]) + moneys[i][j];
int left = Math.abs(moneys[i][j-1]) + moneys[i][j];
if(top >= left) moneys[i][j] = top;
else moneys[i][j] = -left;
}
}
System.out.println("Max path sum = " + Math.abs(moneys[n - 1][n - 1]));
List<List<Integer>> path = new ArrayList<>();
int curri = n-1;
int currj = n-1;
while (curri > 0 || currj > 0) {
path.add(Arrays.asList(curri, currj));
if(moneys[curri][currj] < 0) {
currj -= 1;
// assume: moneys is not null, width and length are equal
int n = moneys.length;
if (n == 0)
return new ArrayList<>();
// base case
for (int j = 1; j < n; j++) {
moneys[0][j] = -(Math.abs(moneys[0][j-1]) + moneys[0][j]);
}
for (int i = 1 ; i < n ; i++) {
moneys[i][0] = moneys[i-1][0] + moneys[i][0];
}
for(int i = 1; i < n ; i++) {
for(int j = 1; j < n ; j++) {
int top = Math.abs(moneys[i-1][j]) + moneys[i][j];
int left = Math.abs(moneys[i][j-1]) + moneys[i][j];
if(top >= left) moneys[i][j] = top;
else moneys[i][j] = -left;
}
}
System.out.println("Max path sum = " + Math.abs(moneys[n - 1][n - 1]));
List<List<Integer>> path = new ArrayList<>();
int curri = n-1;
int currj = n-1;
while (curri > 0 || currj > 0) {
path.add(Arrays.asList(curri, currj));
if(moneys[curri][currj] < 0) {
currj -= 1;
//这里要check一下currj/curri是否到0，否则indexOutOfBound了
} else {
curri -=1;
}
}
path.add(Arrays.asList(0, 0));
return path;
}
} else {
curri -=1;
}
}
path.add(Arrays.asList(0, 0));
return path;
}
follow up：
补充：若机器人只能走右上，右和右下。请问
1. 有三个点需要遍历
2. 如何判断三个点一个是合理的，即存在遍历三个点的路径
3. 给H，需要向下越过H界
思路：
- 用三个点切割矩形，然后每个小块复用之前的方法，最后做乘积 什么叫做用3个点切割矩形哇？就是用起始点到最左点对角线的矩形是第一个矩形，第一点到第二点构成的矩形为第二矩形，以此类推我们就得出三个小矩形，分别计算并乘积
- 切割后的矩形高度不能超过宽度，不然没法走到 为什么高度不能超过宽度哇，我觉得可以啊，感觉前面的点的横纵坐标比后面的切割点的横纵坐标小或者等于才可以遍历所有点，跟矩形高度宽度有什么关系呢，不懂 因为如果高度为5，长度为2 从左上角到右下角走不过去 为啥走不过去啊？就是个矩形，往下面走就好了啊，不懂诶，这个跟矩形高度宽度有啥关系。不好意思，看followup补充。题目略有变动我忘记说了
- 若给定H，先总的dp走一遍，再不越界走一遍（不越界走一遍是什么意思哇 就是用高度为H 宽度相等的矩形再来一遍），相减即可 给定 h是什么意思哇，是高度的意思么？就是给你横着画一条线，然后从左上到右上的所有路线 必须经过这条线或以下的区域
