题目：
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.
Example:
Input: [ [1,3,1], [1,5,1], [4,2,1] ] Output: 7 Explanation: Because the path 1→3→1→1→1 minimizes the sum.亚麻OA基础版。这道题要求从一个二维数组从左上到右下的路径中的最少之和，每次只能往右或者往下走。这道题的做法应该是DP，但我也有考虑过DFS、BFS之类的，不知道是不是想偏了。如果用二维DP做的话非常简单，先把第一行和第一列给定义好，然后剩下的元素就取dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])并加上当前的grid值即可。代码写起来还是非常简单的，时空复杂度都是O(n^2)
C++：运行时间12ms，45.24%，空间10.9M，42.1%：
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); vector<vector<int>> dp(rows, vector<int>(cols, grid[0][0])); for (int i = 1; i < rows; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int j = 1; j < cols; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[rows - 1][cols - 1]; } };这里还学会了二维vector初始化的方法：vector<vector<int>> dp(rows, vector<int>(cols, grid[0][0]));
2020.8.18补Java：
Runtime: 3 ms, faster than 47.06% of Java online submissions for Minimum Path Sum.
Memory Usage: 43.7 MB, less than 8.50% of Java online submissions for Minimum Path Sum.
class Solution { public int minPathSum(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int[][] dp = new int[rows][cols]; dp[0][0] = grid[0][0]; for (int i = 1; i < cols; i++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } for (int i = 1; i < rows; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]); } } return dp[rows - 1][cols - 1]; } }看了discussion发现上面的二维数组还可以优化空间复杂度，只需要用到O(n)。因为每次更新dp[i][j]的时候，我们只需要拥有它左边的那个元素和它上方的元素。因此，我们可以只定义一个vector用来存当前遍历的这一列，每次更新的时候根据上次的更新第一行，后面的就跟它左边和上面的元素进行比较即可（但是这里之前浪费了好长时间不太知道该怎么写）。时间8ms，87.52%，空间10.2M，100%：
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); vector<int> curr(rows, grid[0][0]); for (int i = 1; i < rows; i++) { curr[i] = curr[i - 1] + grid[i][0]; } for (int j = 1; j < cols; j++) { curr[0] += grid[0][j]; for (int i = 1; i < rows; i++) { curr[i] = min(curr[i - 1], curr[i]) + grid[i][j]; } } return curr[rows - 1]; } };2020.8.18补Java：不知道为啥去年说不知道该怎么写，这次倒是看完优化思路以后马上就写出来了，但是有一个小坑卡了一下下，就是那个双重循环里的i和j的顺序问题。
Runtime: 4 ms, faster than 25.99% of Java online submissions for Minimum Path Sum.
Memory Usage: 43 MB, less than 34.28% of Java online submissions for Minimum Path Sum.
class Solution { public int minPathSum(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int[] dp = new int[rows]; dp[0] = grid[0][0]; for (int i = 1; i < rows; i++) { dp[i] = dp[i - 1] + grid[i][0]; } for (int i = 1; i < cols; i++) { for (int j = 0; j < rows; j++) { if (j == 0) { dp[j] += grid[j][i]; } else { dp[j] = Math.min(dp[j - 1] + grid[j][i], dp[j] + grid[j][i]); } } } return dp[rows - 1]; } }对于亚麻那道题：https://leetcode.com/discuss/interview-question/383669/
Given a matrix with r rows and c columns, find the maximum score of a path starting at [0, 0] and ending at [r-1, c-1]. The score of a path is the minimum value in that path. For example, the score of the path 8 → 4 → 5 → 9 is 4.
Don't include the first or final entry. You can only move either down or right at any point in time.
Example 1:
Input: [[5, 1], [4, 5]] Output: 4 Explanation: Possible paths: 5 → 1 → 5 => min value is 1 5 → 4 → 5 => min value is 4 Return the max value among minimum values => max(4, 1) = 4.Example 2:
Input: [[1, 2, 3] [4, 5, 1]] Output: 4 Explanation: Possible paths: 1-> 2 -> 3 -> 1 1-> 2 -> 5 -> 1 1-> 4 -> 5 -> 1 So min of all the paths = [2, 2, 4]. Note that we don't include the first and final entry. Return the max of that, so 4.亚麻这道题要求的是，一个path的score定义为这个path里最小的值，要求所有path的score里的最大的，题目比较绕。还是采用类似的DP的方法，先把第一行和第一列给赋值好，然后对后面的dp[i][j]，状态转移方程采用：dp[i][j] = max(min(dp[i - 1][j], grid[i][j]), min(dp[i][j - 1], grid[i][j]))，相当于就是一个dp二维矩阵中的元素，采用到它的两个路径中上一个节点和它自己比较的较小值（也就是到这一个元素的score）中的较大的（也就是更大的score），另外注意第一个节点和最后一个节点是不算数的，因此要特殊处理一下。代码：
// Given a matrix with r rows and c columns, find the maximum score of a path starting at [0, 0] and ending at [r - 1, c - 1]. The score of a path is the minimum value in that path. For example, the score of the path 8 → 4 → 5 → 9 is 4. #include <iostream> #include <string> #include <vector> #include <limits.h> using namespace std; int maxScore(vector<vector<int> >& grid){ int rows = grid.size(); int cols = grid[0].size(); vector<vector<int>> dp(rows, vector<int>(cols, grid[0][0])); dp[0][1] = grid[0][1]; dp[1][0] = grid[1][0]; for (int i = 2; i < rows; i++) { dp[i][0] = min(dp[i - 1][0], grid[i][0]); } for (int i = 2; i < cols; i++) { dp[0][i] = min(dp[0][i - 1], grid[0][i]); } for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { if (!((i == rows - 1) && (j == cols - 1))) { dp[i][j] = max(min(grid[i][j], dp[i - 1][j]), min(grid[i][j], dp[i][j - 1])); } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[rows - 1][cols - 1]; //return 0; } int main() { // Testing vector<vector<int>> grid1 {{5, 1}, {4, 5}}; vector<vector<int> > grid0 {{1, 2, 3}, {4, 5, 1}}; vector<vector<int> > grid2 {{5, 1, 7}, {4, 8, 5}}; vector<vector<int> > grid3 {{1, 9, 9}, {9, 9, 9}, {9, 9, 9}}; vector<vector<int> > grid4 {{10, 7, 3}, {12, 11, 9}, {1, 2, 8}}; vector<vector<int> > grid5 {{20, 20, 3}, {20, 3, 20}, {3, 20, 20}}; cout << "Max score should be 4: " << maxScore(grid1) << "\n"; cout << "Max score should be 4: " << maxScore(grid0) << "\n"; cout << "Max score should be 4: " << maxScore(grid2) << "\n"; cout << "Max score should be 9: " << maxScore(grid3) << "\n"; cout << "Max score should be 9: " << maxScore(grid4) << "\n"; cout << "Max score should be 3: " << maxScore(grid5) << "\n"; }Java：
public class MaxMinScore { public static int maxMinScore(int[][] matrix) { int rows = matrix.length; int cols = matrix[0].length; int[][] dp = new int[rows][cols]; dp[0][0] = Integer.MAX_VALUE; for (int i = 1; i < rows; i++) { dp[i][0] = Math.min(dp[i - 1][0], matrix[i][0]); } for (int i = 1; i < cols; i++) { dp[0][i] = Math.min(dp[0][i - 1], matrix[0][i]); } for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { if (i == rows - 1 && j == cols - 1) { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } else { dp[i][j] = Math.max(Math.min(matrix[i][j], dp[i - 1][j]), Math.min(matrix[i][j], dp[i][j - 1])); } } } return dp[rows - 1][cols - 1]; } public static void main(String[] args) { int[][] matrix1 = {{5, 1}, {4, 5}}; int[][] matrix2 = {{1, 2, 3}, {4, 5, 1}}; int[][] matrix3 = {{5, 1, 7}, {4, 8, 5}}; int[][] matrix4 = {{1, 9, 9}, {9, 9, 9}, {9, 9, 9}}; int[][] matrix5 = {{10, 7, 3}, {12, 11, 9}, {1, 2, 8}}; int[][] matrix6 = {{20, 20, 3}, {20, 3, 20}, {3, 20, 20}}; System.out.println("should be 4: " + maxMinScore(matrix1)); System.out.println("should be 4: " + maxMinScore(matrix2)); System.out.println("should be 4: " + maxMinScore(matrix3)); System.out.println("should be 9: " + maxMinScore(matrix4)); System.out.println("should be 9: " + maxMinScore(matrix5)); System.out.println("should be 3: " + maxMinScore(matrix6)); } }
