题解 | #矩阵的最小路径和#
矩阵的最小路径和
http://www.nowcoder.com/practice/7d21b6be4c6b429bb92d219341c4f8bb
思路：
最核心的一步，也是题目的突破口，就是找到状态转移方程。
定义dp[i][j]为走到matrix[i][j]这个数的最小路径和，则状态转移方程为：
dp[i][j]=min{dp[i][j-1],dp[i-1][j],dp[i+1][j],dp[i][j+1]}+matrix[i][j]
其意思就是找到当前这个数上下左右中路径和最小的那条路径，然后再加上当前这个数，作为到达当前这个数的最小路径和
base case：dp[0][0]=matrix[0][0]
除了上述核心思路，还要解决边界问题，因为可能发生数组索引越界，为了解决这个问题，就应该对dp数组扩容
，比很多社招五六年的都强那种
投递阿里巴巴集团等公司9个岗位