首页 > 代码库 > leetcode. Minimum Path Sum
leetcode. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
建立新的数组path[m][n], 对于path[i][j]:
path_arr[i][j] = min(path_arr[i - 1][j], path_arr[i][j - 1]) + grid[i][j];1 int minPathSum(vector<vector<int> > &grid) 2 { 3 int m = grid.size(); 4 if (m <= 0) 5 return 0; 6 int n = grid[0].size(), i, j, result; 7 int **path_arr = new int* [m]; 8 for (i = 0; i < m; i++) 9 {10 path_arr[i] = new int[n];11 }12 13 for (i = 0; i < m; i++)14 {15 for (j = 0; j < n; j++)16 {17 if (i == 0 && j == 0)18 path_arr[i][j] = grid[i][j];19 else if (i == 0 && j > 0)20 path_arr[i][j] = grid[i][j] + path_arr[i][j - 1];21 else if (i > 0 && j == 0)22 path_arr[i][j] = grid[i][j] + path_arr[i - 1][j];23 else24 path_arr[i][j] = min(path_arr[i - 1][j], path_arr[i][j - 1]) + grid[i][j];25 }26 }27 result = path_arr[m - 1][n - 1];28 for (i = 0; i < m; i++)29 {30 delete[] path_arr[i];31 }32 delete[] path_arr;33 return result;34 }
leetcode. Minimum Path Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。