这一组题目都非常相似，其实就是遍历数组，不管是长方形的，还是三角形的，遍历的过程中更新状态，并用dp数组记录。 dp数组都可以从二维的优化到一维的。但是需要注意，更新dp[i]的时候，dp[i]依赖的元素，如果是上一轮更新的结果，那么这个元素要在dp[i]之后更新；如果这个元素应该是新一轮更新的结果，那么这个元素要在dp[i]之前更新——这个决定了更新的方向，是从后往前还是从前往后。

最小路径和

64. 最小路径和

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

其实这个题还是非常简单的！到一个点只能通过左边和上边两个点，如果用dp这个二维数组进行状态转移的话，dp[i][j]就是到这个点需要的最小路径和，更新过程：dp[i][j] = min( dp[i-1][j], dp[i-1][j])。

原地修改数组

直接在原来的数组grid上更新，这样虽然解决了空间复杂度，但是在实际业务中，修改原数组是很危险的（原数组可能在很多地方有其他用处，而且java是面向对象的，传入的数组是引用……）。
java代码如下：

class Solution {public int minPathSum(int[][] grid) {int row = grid.length; // get number of rowsint col = grid[0].length; // get number of columns// 第一列只能从下网上for(int i = 1; i < row; i++)grid[i][0] += grid[i-1][0];//第一行只能从左往右for(int j = 1; j < col; j++)grid[0][j] += grid[0][j-1];// 更新其他点for(int i = 1; i < row; i++)for(int j = 1; j < col; j++){grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);}return grid[row-1][col-1];}
}

定义二维数组进行状态转移

定义一个和原数组一样大小的二维数组，进行状态转移，其实和上面是一样的，只是需要一个新的数组。
java代码如下：

class Solution {public int minPathSum(int[][] grid) {int row = grid.length; // get number of rowsint col = grid[0].length; // get number of columnsint[][] pathCount = new int[row][col];pathCount[0][0] = grid[0][0];for(int i = 1; i < row; i++)pathCount[i][0] = grid[i][0] + pathCount[i-1][0];for(int j = 1; j < col; j++)pathCount[0][j] =  grid[0][j] + pathCount[0][j-1];        for(int i = 1; i < row; i++)for(int j = 1; j < col; j++){pathCount[i][j] = grid[i][j] + Math.min(pathCount[i-1][j], pathCount[i][j-1]);}return pathCount[row-1][col-1];}
}

优化：用 一维数组进行状态转移

二维状态转移数组，其实每一行只在计算第二行的用到，因此可以之际用一维的，此时更新过程：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]。 遍历的时候一维dp还是从前往后，dp[i]依赖于dp[i-1]，而dp[i-1]确实需要先更新。
java代码如下：

class Solution {public int minPathSum(int[][] grid) {int row = grid.length; // get number of rowsint col = grid[0].length; // get number of columnsint[] pathCount = new int[col];Arrays.fill(pathCount ,Integer.MAX_VALUE);pathCount[0] = 0;        for(int i = 0; i < row; i++)for(int j = 0; j < col; j++){if(j > 0)pathCount[j] = grid[i][j] + Math.min(pathCount[j], pathCount[j-1]);elsepathCount[j] += grid[i][j] ;}return pathCount[col-1];}
}

相似题目：LCR 166. 珠宝的最高价值

LCR 166. 珠宝的最高价值

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

这题和最小路径和，是一模一样的，只是换了个场景罢了。

class Solution {public int jewelleryValue(int[][] frame) {int m = frame.length, n = frame[0].length;int[][] dp = new int[m][n];for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (i > 0) {dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);}if (j > 0) {dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);}dp[i][j] += frame[i][j];}}return dp[m - 1][n - 1];}
}

120. 三角形最小路径和

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

这个题目和上面的题目不同的点在于，这是一个三角形的结构，且一行的状态完全由上一行的节点状态相关。题目中说上一行节点i下次移动到下一行的i或者i+1，那么对于下一行i，其实是由i-1和i中较小值移动来的。
经过上面的分析假设用二维数组dp表示状态转移，那么dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。

原地修改数组

可以直接在triangle数组上进行状态转移。java代码如下。需要注意的是java中的<List<List<>>>这样的数据结构，之前没咋用，不能直接用下标，需要用set()和get()方法。

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int row = triangle.size(); // 如果只有一行，直接返回if(row == 1) return triangle.get(0).get(0);for(int i = 1; i < row; i++){for(int j = 0; j < i; j++){//第一列只能由上方的点转移来if(j==0)  triangle.get(i).set(0, triangle.get(i).get(0) + triangle.get(i-1).get(0));// 其他点由其上方和左上方两个中较小的决定elsetriangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i-1).get(j-1), triangle.get(i-1).get(j)));}//最后一个点只能由左上方的点转移来triangle.get(i).set(i, triangle.get(i).get(i) + triangle.get(i-1).get(i-1));}//最后一行的最小值为结果int count = triangle.get(row-1).get(0);for(int i =1; i < row; i++)count = Math.min(count,triangle.get(row-1).get(i));return count;}
}

定义二维数组进行状态转移

修改原始数据会有很多潜在威胁，还是定义一个新的二维数组进行状态转移：

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int row = triangle.size(); if(row == 1) return triangle.get(0).get(0);// 定义新的数组int dp[][] = new int[row][row];dp[0][0] = triangle.get(0).get(0);for(int i = 1; i < row; i++){//单独处理每行第一个，其只能由上一行第一个转移而来dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);// 正常处理，由上一行的j-1和j较小的一个转移而来for(int j = 1; j < i ; j ++)dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);//每行最后一个只能由上一行最后一个转移而来dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);}int count = dp[row-1][0];for(int i =1; i < row; i++)count = Math.min(count,dp[row-1][i]);return count;}
}

一维数组进行状态转移

同样的，我们也可以考虑用一维数组进行状态转移，优化空间复杂度，但是需要注意的是，这个题目，更新一维状态数组的时候，需要从后往前！ 因为dp[j] = min(dp[j-1], dp[j]) + triangle[i][j]的时候，dp[j-1]应该是上一轮更新的结果，表示上一行的结果；如果从前往后，dp[j-1]以及在这一轮更新过了。因此整体的更新防线：自顶向下；某一层的更新方向（dp状态数组的更新方向）从后往前。
Java代码如下：

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int row = triangle.size(); if(row == 1) return triangle.get(0).get(0);int dp[] = new int[row];dp[0] = triangle.get(0).get(0);for(int i = 1; i < row; i++){dp[i] = dp[i-1] + triangle.get(i).get(i);for(int j = i -1; j> 0 ; j--)dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);dp[0] = dp[0] + triangle.get(i).get(0);}int count = dp[0];for(int i =1; i < row; i++)count = Math.min(count,dp[i]);return count;}
}

自底向上，反方向进行状态转移

题意中，上一层下标为i的，可以传递到下一层下标为i和i+1的。可以考虑将这个传递方向反过来，直接从最后一行开始，从下往上传递，最后到triangle[0][0]，得到的就是最终的答案！从下一层到上一层，状态转移为：dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];，也就是说上一层下标为i的元素，由下一层下标为i和i+1的元素影响，这其实就是题意的意思。整体的更先方向是自底向上的， 一行中的更新方向是从前往后的。
Java代码：

class Solution {public int minimumTotal(List<List<Integer>> triangle) {int row = triangle.size(); if(row == 1) return triangle.get(0).get(0);int dp[] = new int[row];// 将三角形最后一行赋值给dp状态数组for(int i = 0; i < row; i++)dp[i] = triangle.get(row-1).get(i);//从下往上更新for(int i = row - 2; i >=0 ; i--){//每一层从前往后更新for(int j = 0; j <= i ; j++)dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);}return dp[0];    }
}

931. 下降路径最小和

931. 下降路径最小和

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

根据题意，row行col列的元素，往下可以传递到row+1行的col-1、col以及col+1列，那么对于row+1行的col列，可以从row上的col-1、col以及col+1列传递来，因此定义二维的状态转移数组dp，转移过程：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1] + matrix[i][j]。注意边界，第一列和最后一列只能由上一行的两个元素传递来。
java代码如下：

class Solution {public int minFallingPathSum(int[][] matrix) {int n = matrix.length;int[][] dp = new int[n][n];// 第一行直接赋值for(int i = 0; i < n; i++)dp[0][i] = matrix[0][i];for(int i=1; i<n; i++){// 第一列的特殊情况dp[i][0]= Math.min(dp[i-1][0],dp[i-1][1]) + matrix[i][0];for(int j = 1;j < n-1; j++){dp[i][j] = matrix[i][j] + Math.min(dp[i-1][j-1], Math.min(dp[i-1][j+1],dp[i-1][j]));}// 最后一列的特殊情况dp[i][n-1] = matrix[i][n-1] + Math.min(dp[i-1][n-1],dp[i-1][n-2]);}int ans = dp[n-1][0];for(int i =1; i<n;i++)if(dp[n-1][i]<ans)ans = dp[n-1][i];        return ans;}
}

1289. 下降路径最小和 II

1289. 下降路径最小和 II

给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

这个题目说得天花乱坠的，其实就是row行选了col列，那么row-1行和row=1行都不能选col列，除了col列的其他行都能选择。 这个也可以用二维的dp数组进行状态转移：dp[i][j] = grid[i][j] + min(dp[i-1][k]) k≠j。也就是说，针对一行的每个元素，找到除这个列意外的，dp[i-1]中的最小值即可，代码中可以用三层循环实现：

for(int i = 0; i < row; i++) //遍历行for(int j = 0; j < col; j++) // 遍历列for(………………)//找dp[i-1]中非j列的min //update dp[i][j]

优化分析：

• 每次找dp[i-1]行中的最小值除了j列以外的最小值，其实除了最小值对应的minIndex列以外的列，找到的最小值就是dp[i-1]整个行的最小值。而最小值minIndex对应列，要找的最小值，是整个dp[i-1]中的第二个最小值。
• 最终要求返回的是路径最小和，也就是对最后一行dp[row-1]更新后的最小值。因此我们只需要用一个firstMin变量记录每一行的最小值即可（循环更新的，每一层遍历一行就会更新），最后返回这个值即可。
  最终状态转移：
  
  Java代码如下：

class Solution {public int minFallingPathSum(int[][] grid) {int row = grid.length;int col = grid[0].length; // 记录上一行结果的最小值和第二最小值，以及最小值对应的下标   int firstMin = 0; int secondMin = 0; int firstIndex = -1;for(int i = 0; i < row; i++){//记录当前行结果的最小值、第二最小值，以及最小值对应的下标int curFirMin = Integer.MAX_VALUE;int curSecMin = Integer.MAX_VALUE;int curFirIndex = -1;for(int j = 0; j < col; j++){//curSum就是dp[j]int curSum = (j != firstIndex ? firstMin : secondMin) + grid[i][j];if(curSum < curFirMin){curSecMin = curFirMin;curFirMin = curSum;curFirIndex = j;}else if(curSum < curSecMin)curSecMin = curSum;}//用这一轮结果更新上一轮结果firstIndex = curFirIndex;firstMin = curFirMin;secondMin = curSecMin;}return firstMin; //最终返回firstMin即可}
}