图文网站源码,泉州晋江网站建设费用,一个公司可以备案几个网站,信息网站 微站给定一个包含非负整数的 m x n 网格 grid #xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。
说明#xff1a;每次只能向下或者向右移动一步。
思路一#xff1a;动态规划
int minPathSum(int** grid, int gridSize, int* gridColSi…给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。
思路一动态规划
int minPathSum(int** grid, int gridSize, int* gridColSize){int m gridSize,n *gridColSize;int dp[m][n];dp[0][0] grid[0][0];for (int i 1;i m;i) {dp[i][0] dp[i - 1][0] grid[i][0];}for (int i 1;i n;i) {dp[0][i] dp[0][i - 1] grid[0][i];}for(int i 1;im;i){for(int k 1;kn;k){dp[i][k] fmin(dp[i - 1][k], dp[i][k - 1]) grid[i][k];}}return dp[m-1][n-1];
}
时间复杂度O(n^2)空间复杂度O(n^2)
分析
本题也是寻找路径问题可使用动态规划进行解答先设置dp[0][0]第一列每一步等于上一步加上grid值同理第一行也这样处理再通过比较上一个值和左一个值谁小来决定dp下一位的值最后返回右下角的dp[m-1][n-1]
总结
本题考察动态规划的应用为经典的动态规划查找最小路径问题正确应对限制条件即可做出。
