题意理解 从矩阵的(0,0)位置开始,向右或者向下移动到(n-1, m-1)位置,求经过的位置上的数字之和的最小值。 方法一(动态规划) 动态规划要求整体的最优解可以由子问题的最优解得到。使用表示从(0,0)到(i,j)的路径和。本题中,(i,j)只能从(i-1,j)或者(i,j-1)走过来,我们只要选择其中dp值较小的路径。(注意这里的子问题不是和的最小值)所以动态规划的公式为: 边界条件有:1、2、第0行和第0列的各个位置只能从前一个位置走过来, 算法示意图如下:最后可以发现,每个位置(i,j)只经过一次,所以经过时可以把更新为从(0,0)到(i,j)的最短路径...