婚纱网站论文,农村电商平台网站设计思路有哪些,谷歌网站优化工具,音乐门户网站模板又是一道动态规划基础例题。
题目 这道题可以类似不同路径。先把左上角格子进行填充#xff0c;然后用一个数组去更新每走到一个格的数字总和#xff0c;首先处理边界问题#xff0c;把最左边的列只能由上方的行与原来的格子数值的和#xff0c;同理#xff0c;最上方的行…又是一道动态规划基础例题。
题目 这道题可以类似不同路径。先把左上角格子进行填充然后用一个数组去更新每走到一个格的数字总和首先处理边界问题把最左边的列只能由上方的行与原来的格子数值的和同理最上方的行只能由作左边的行与原来的格子数值的和然后像上次路径dp那样做遍历直到取出右下角的坐标的数值即可。
class Solution {public int minPathSum(int[][] grid) {// f[m][n] Math.min(f[m-1][n],f[m][n-1]) grid[m][n]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 m ; i ) {dp[i][0] grid[i][0]dp[i-1][0];}for ( int i 1 ; i n ; i ) {dp[0][i] grid[0][i] dp[0][i-1];}for ( int i 1 ; i m ; i ) {for ( int j 1 ; j n ; j ) {dp[i][j] grid[i][j] Math.min(dp[i-1][j],dp[i][j-1]);}}return dp[m-1][n-1];}
}
也可以优化成滚动数组。
class Solution {public int minPathSum(int[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) {return 0;}int rows grid.length, columns grid[0].length;// 创建一个一维数组 dp 来存储每一行的路径和int[] dp new int[columns];dp[0] grid[0][0]; // 起点处的最小路径和for (int j 1; j columns; j) {dp[j] dp[j - 1] grid[0][j];}for (int i 1; i rows; i) {// 第一列的位置路径只能从上方来dp[0] grid[i][0];for (int j 1; j columns; j) {dp[j] Math.min(dp[j], dp[j - 1]) grid[i][j];}}// 最终的结果在 dp[columns - 1] 中表示右下角的最小路径和return dp[columns - 1];}
}典型路径动态规划助你找准最好的路径。
