给定一个 n * m 的矩阵 a,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,输出所有的路径中最小的路径和。
数据范围: ,矩阵中任意值都满足
要求:时间复杂度
例如:当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时,对应的返回值为12,
所选择的最小累加和路径如下图所示:
[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]
12
[[1,2,3],[1,2,3]]
7
/** * * js实现 */ function minPathSum( matrix ) { // write code here 动态规划, let dp = new Array(matrix.length).fill(0).map(item => new Array(matrix[0].length)); dp[0][0] = matrix[0][0]; for(let i = 1; i < matrix.length; i++) { dp[i][0] = dp[i-1][0] + matrix[i][0]; } for(let i = 1; i < matrix[0].length; i++) { dp[0][i] = dp[0][i-1] + matrix[0][i]; } for(let i = 1; i < matrix.length; i++) { for(let j = 1; j < matrix[0].length; j++) { dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]; } } return dp[matrix.length - 1][matrix[0].length - 1]; }
function minPathSum( matrix ) { if (matrix.length === 0) return 0; const [n, m] = [matrix.length, matrix[0].length]; const dp = Array.from(new Array(n), () => new Array(m).fill(0)); dp[0][0] = matrix[0][0]; for (let i = 1; i < m; i++) dp[0][i] = dp[0][i - 1] + matrix[0][i]; for (let i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + matrix[i][0]; for (let i = 1; i < n; i++) { for (let j = 1; j < m; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]; } } return dp[n - 1][m - 1]; }
var minPathSum = function(matrix) { let m = matrix.length, n=matrix[0].length if(!m ||!n) return 0 for(let i = 0;i<m;i++){ for(let j = 0;j<n;j++){ if(i==0&&j>0){ matrix[0][j] += matrix[0][j-1] }else if(i>0&&j==0){ matrix[i][0] +=matrix[i-1][0] }else if(i>0&&j>0){ matrix[i][j] += Math.min(matrix[i-1][j],matrix[i][j-1]) } } } return matrix[m-1][n-1] };