有一个由数字组成的规格为 n × m n\times m n×m 的矩阵，初始在左上角，要求每次只能向下或向右移动，问该数字矩阵从最左上角到最右下角的最小路径和是多少？（路径和就是将某路径中的所有权值全部加起来的总和）

这类题会很自然地想到用暴力搜索法，但是暴力法在数据范围过大的情况下是难以胜任的。出现这种情况的原因和斐波那契数列中的递归法一样——会出现大量的重复工作，耗费大量时间。 比如对于某个数字矩阵：

1 3 5 7 8 6 4 2 5 0 1 3 4 8 7 2 \begin{equation*} \begin{matrix} 1 & 3 & 5 & 7\\ 8 & 6 & 4 & 2\\ 5 & 0 & 1 & 3\\ 4 & 8 & 7 & 2 \end{matrix} \end{equation*} 1854​3608​5417​7232​​

从位置（1，1）到（3，3）这之间存在的路径有以下六条：

因此，在利用暴力法从位置 ( 1 , 1 ) (1,1) (1,1) 到位置 ( 3 , 3 ) (3,3) (3,3) 处，再到最右下角位置 ( 4 , 4 ) (4,4) (4,4) 时，我们都需要尝试这六种走法，并分别与路径 1 → 3 → 2 1→3→2 1→3→2 以及 1 → 7 → 2 1→7→2 1→7→2 进行求和后再比较并求出其中的最短路，可见这样的算法是极其低效的。而优化的方法也正是通过生成一个和原矩阵大小相同的二维表，来将从起点到每个位置的最小路径和记录下来，进而以直接取值来替代多次重复递归来达到优化目的。下面详细介绍一下该算法的具体实现。

首先我们需要来填写一张和题目中给出的矩阵大小相同的表格，如下：

第一步：初始化。由于在上侧和左侧的边界位置（即最上方一行和最左边一列），其路径只有一条（最上方的每个格子的前一个格子只能来自左方、最左边的每个格子的前一个格子只能来自上方），我们别无选择，因此可以直接填写，如下：

第二步：确定某个位置的最小路径和。拿位置坐标为 ( 2 , 2 ) (2,2) (2,2) 的这个点来说，由于走到这一点只能来自其上方或左方，因此为了使得走到这一点时的路径和最小就需要从其上方或左方中选出值较小的那个点作为其前驱结点。于是我们在填写位置坐标为 ( 2 , 2 ) (2,2) (2,2) 这个点的最小路径和时，所用的公式为：

d p [ 2 , 2 ] = m i n ( d p [ 2 , 1 ] , d p [ 1 , 2 ] ) + v a l u e [ 2 , 2 ] = m i n ( 9 , 4 ) + 6 = 4 + 6 = 10 dp[2,2] = min(dp[2,1],dp[1,2]) + value[2,2] = min(9,4) + 6 = 4+6 =10 dp[2,2]=min(dp[2,1],dp[1,2])+value[2,2]=min(9,4)+6=4+6=10

其中 d p [ x , y ] dp[x,y] dp[x,y] 表示位置坐标为 ( x , y ) (x,y) (x,y) 的最小路径和， v a l u e [ x , y ] value[x,y] value[x,y] 表示位置坐标为 ( x , y ) (x,y) (x,y) 的权值。 于是，现在的表格内容如下：

接下来继续执行这个过程，直到该表格的所有空格都填写完，那么最终 d p [ n , m ] dp[n,m] dp[n,m] 中的内容即为我们所需的答案。 回看上面的过程，不难得出求解本题的状态转换方程为：

d p [ i ] [ j ] = m i n ( d p [ i ] [ j − 1 ] , d p [ i − 1 ] [ j ] ) + v a l u e [ i ] [ j ] dp[i][j] = min( dp[i][j-1],dp[i-1][j] ) + value[i][j] dp[i][j]=min(dp[i][j−1],dp[i−1][j])+value[i][j]

下面给出求解本题的完整代码：