给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]] 输出:7 解释:因为路径 1→3→1→1→1 的总和最小。
思路:
也没啥好说的,还是动规,还是老套路。直接做就行了
复杂度:
时间复杂度:遍历O(mn)
空间复杂度:dp数组O(mn)
代码:public int minPathSum(int[][] grid) { //动规数组dp[][]表示到ij的最小和 int m = grid.length; int n = grid[0].length; int dp[][] = new int[m][n]; //初始化第一行第一列 dp[0][0] = grid[0][0]; for(int i=1;i
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)