继续打卡算法题，今天学习的是LeetCode第64题最小路径和，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对我们的编码思维和编码能力有一些提升。
分析一波题目
哈哈，不管什么题目，先看看能不能穷举出来，这个题目求最小路径和，我们一样可以将所有可能的路径列出来，然后取里面的最短的。这样是可行的，但是这样需要把所有的路径记录下来，可能会重复遍历很多路径，这样效率就低了。
通过穷举，发现本题也是有规律的，
1、每第一行的元素，只能左边的元素向右移动到达
2、第一列的元素，只能上面的元素移动到达
2、个位置只能通过上一个。位置向下走，或者左边的位置向右边移动达到
下图箭头方向，就是可以推算的方向，比如元素5位置，只能通过元素3位置，和元素1移动到
从上图可以看出，我们的最短路径只能是两个方向的路径最短，并且发现到达后面的元素路径通过上方和左方的元素推导出来。
这种根据子问题推导求解的算法，是动态规划。
我们可以使用二维数组dp[i][j]表示，到ij的最短路径，
第一行的情况，都是dp[0][j-1] + grid[0][j]
第一列的情况，都是dp[i-1][0] + grid[i][0]
其他情况，只能是min(dp[i-1][j],dp[i][j-1])，这就是动态方程函数。
本题解题技巧
1、根据前一个位置或者上一个位置推导出当前位置的最短路径
编码解决
class Solution {
public int minPathSum(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length, columns = grid[0].length;
int[][] dp = new int[rows][columns];
//第一个位置，就是第一个数
dp[0][0] = 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 < columns; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
//非第一列，非第一行的情况
for (int i = 1; i < rows; i++) {
for (int j = 1; j < columns; j++) {
//取最短的一个路径
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
//返回最后一个位置的最短路径
return dp[rows - 1][columns - 1];
}
}
总结
1、此题是使用动态规划思想解决，我们发现问题的解是由上一个情况的问题求解推导出来的。如果我们不理解动态规划思想，那么可以回忆一下斐波拉契数列求解过程,他也是通过前面的解一步一步求出当前的解。
