给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
昨天做了道算法题，感觉画图很有助于自己理解算法的过程，这次再挑一个算法加深印象。碰到这种类型的题目，和递归很像，但是使用递归，如果数据范围比较大，就会花费很长时间。
动态规划(英语：Dynamic programming，简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
废话少说
解题
根据题意，到达网格中的某个点最短，可以理解为网格中的任何一个点都是可以走过去的，而且任何一个网格都有一个最短的路径。
那么我们使用一种数据结构保存，从顶点到达网格中任意一点的最短位置。根据人的正常逻辑，画图如下：
从顶点按照行来遍历每一个位置，计算每一个位置的最小路径
image-20190320161330569
根据上面的图片可以了解：
当点处于第一行的时候，它的最短路径就是同一行的前一个位置加上当前位置
当点处于第一列的时候，它的最短路径就是上一行的位置加上当前位置
当点处于顶点的时候，它就是顶点的值
当点位于中间的位置，它是其上一行或上一列的最小值加上当前的值
至此，我们写程序如下：
public static int minPathSumAi(int[][] grid){
// 特殊情况处理
if (grid.length == 0){
return 0;
}
// 新建一个标记数组，标记到每个位置的最短路径
int xLen = grid.length;
int yLen = grid[0].length;
int[][] markBit = new int[xLen][yLen];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
// 初始位置
if (i == 0 && j == 0){
markBit[i][j] = grid[i][j];
}
// 当点在第一行的位置时
else if (i == 0){
markBit[i][j] = markBit[i][j-1] + grid[i][j];
}
// 当点在第一列的位置时
else if (j == 0){
markBit[i][j] = markBit[i-1][j] + grid[i][j];
}
// 当点在数组的中间位置时
else {
markBit[i][j] = Math.min(markBit[i-1][j] , markBit[i][j-1]) + grid[i][j];
}
}
}
return markBit[xLen-1][yLen-1];
}
然后到LeetCode上测试，性能有待于提升，后续水平提高之后再想更优的方案吧，目前先理解解题方式。
image-20190320161740838
最后
程序的运行都是人控制的，在程序运行之前，确保你自己的逻辑清晰，画图可以帮你理清逻辑。
参考