34.矩阵最小路径和

题目详情：

给定一个矩阵，大小为m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置。路径中所有数字累加起来就是路径和，返回所有路径的最小路径和。

解题思路：

本题可以用动态规划的方法来解决。

计算一个格子到右下角的最小路径需要两个数据，一个是右边格子到右下角的最小路径，一个是下边格子到右下角的最小路径，两个数据的较小值加上当前格子的数值即为最小路径。

即 dp[i, j] = min(dp[i + 1, j], dp[i, j + 1]) + m[i, j]

由于计算当前格子最小路径需要右边和下边格子的最小路径。因此，需要从底向上进行决策。

本题用动态规划法的难点之一是从底向上进行决策的顺序。

如下图所示，通过观察可以发现，同一对角线上的数字的横纵坐标和是相等的，我们以对角线的方向为顺序，从右下角向左上角计算出每个格子的最小路径。最后可计算得出 dp[0, 0]。