这是一道算法面试题，不妨看看

动态规划

要想从start 点到 finish 点，那么，必然经过 h1 或 h2 点，所以，问题转化为：求 start 点到 h1 点，或 start 点到 h2点的路径中的较小者，这相当于将问题域变小了1，递归下去，直到问题域变为 1 个点，如下图所示，

这是动态规划思想的典型运用，以下是一版 C# 代码的实现，熟悉 JAVA 的看这些代码也没有问题。

public int MinPathSum(int[,] grid) { int m=grid.GetUpperBound(0)+1; //0-dimension element size int n=grid.GetUpperBound(1)+1; //1-dimension element size int[,] sumdp = new int[m,n]; sumdp[0,0]=grid[0,0]; //two boundaries: for (int i = 1; i < m; i++) sumdp[i,0] = sumdp[i-1,0]+grid[i,0]; for (int i = 1; i < n; i++) sumdp[0,i] = sumdp[0,i-1]+grid[0,i]; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { sumdp[i, j] = Math.Min(sumdp[i - 1, j], sumdp[i, j - 1]) + grid[i,j]; } } return sumdp[m - 1, n - 1]; }

动态规划思想最重要的两个点：

• 找出迭代方程， sumdp[i, j] = Math.Min(sumdp[i - 1, j], sumdp[i, j - 1]) + grid[i,j];
• 空间复杂度换取时间复杂度，代码中的 int[,] sumdp = new int[m,n];

总结

动态规划思想，是算法面试中经常问到的，大家可以详细参考相关链接中的文章再具体了解下什么样的问题适合用动态规划思想来求解，以及动态规划求解的两个点。

希望大家接下来面试算法岗，被问到动态规划问题时，准确击中要害，成为自己的加分项。

相关链接

动态规划|算法

动态规划|前篇：括号知多少

动态规划|中篇：爬楼梯

动态规划|后篇：考量适用指标

动态规划|约束条件下的三角最短路径

动态规划|相邻约束下的最优解

动态规划|相邻约束下的最优解(House Robber II )