精华内容
下载资源
问答
  • 2020-07-31 09:13:57

    三角形最小路径和

    给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

    相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

    例如,给定三角形:

    [
         [2],
        [3,4],
       [6,5,7],
      [4,1,8,3]
    ]
    

    自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

    说明:
    如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    思路一:动态规划

    我们用 f[i][j]表示从三角形顶部走到位置 (i,j) 的最小路径和。这里的位置 (i,j) 指的是三角形中第 i 行第 j 列(均从 0 开始编号)的位置。

    由于每一步只能移动到下一行「相邻的节点」上,因此要想走到位置 (i,j),上一步就只能在位置 (i−1,j−1) 或者位置 (i−1,j)。我们在这两个位置中选择一个路径和较小的来进行转移,状态转移方程为:

    f[i][j]=min⁡(f[i−1][j−1],f[i−1][j])+c[i][j]

    其中 c[i][j] 表示位置 (i,j) 对应的元素值。

    注意第 i 行有 i+1个元素,它们对应的 j 的范围为 [0,i]。当 j=0或 j=i 时,上述状态转移方程中有一些项是没有意义的。例如当 j=0 时,f[i−1][j−1]没有意义,因此状态转移方程为:

    f[i][0]=f[i−1][0]+c[i][0]

    即当我们在第 i 行的最左侧时,我们只能从第 i−1 行的最左侧移动过来。当 j=i时,f[i−1][j] 没有意义,因此状态转移方程为:

    f[i][i]=f[i−1][i−1]+c[i][i]

    即当我们在第 i 行的最右侧时,我们只能从第 i−1 行的最右侧移动过来。

    最终的答案即为 f[n−1][0] 到 f[n−1][n−1]中的最小值,其中 n 是三角形的行数。

    细节

    状态转移方程的边界条件是什么?由于我们已经去除了所有「没有意义」的状态,因此边界条件可以定为:

    f[0][0]=c[0][0]

    即在三角形的顶部时,最小路径和就等于对应位置的元素值。这样一来,我们从 1 开始递增地枚举 i,并在 [0,i] 的范围内递增地枚举 j,就可以完成所有状态的计算。

    作者:LeetCode-Solution
    链接:https://leetcode-cn.com/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
    来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    代码实现一:

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            vector<vector<int>> f(n, vector<int>(n));
            f[0][0] = triangle[0][0];
            for (int i = 1; i < n; ++i) {
                f[i][0] = f[i - 1][0] + triangle[i][0];
                for (int j = 1; j < i; ++j) {
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
                }
                f[i][i] = f[i - 1][i - 1] + triangle[i][i];
            }
            return *min_element(f[n - 1].begin(), f[n - 1].end());
        }
    };
    
    
    > 作者:LeetCode-Solution
    > 链接:https://leetcode-cn.com/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
    > 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
    

    复杂度分析

    时间复杂度:O(n^2),其中 n 是三角形的行数。
    
    空间复杂度:O(n^2)。我们需要一个 n∗n 的二维数组存放所有的状态。
    

    思路二:动态规划 + 空间优化

    在题目描述中的「说明」部分,提到了可以将空间复杂度优化至 O(n)O(n)O(n)。

    我们回顾方法一中的状态转移方程,可以发现,f[i][j] 只与 f[i−1][…] 有关,而与 f[i−2][…] 及之前的状态无关,因此我们不必存储这些无关的状态。具体地,我们使用两个长度为 n 的一维数组进行转移,将 i 根据奇偶性映射到其中一个一维数组,那么 i−1 就映射到了另一个一维数组。这样我们使用这两个一维数组,交替地进行状态转移。

    代码实现

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            vector<vector<int>> f(2, vector<int>(n));
            f[0][0] = triangle[0][0];
            for (int i = 1; i < n; ++i) {
                int curr = i % 2;
                int prev = 1 - curr;
                f[curr][0] = f[prev][0] + triangle[i][0];
                for (int j = 1; j < i; ++j) {
                    f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
                }
                f[curr][i] = f[prev][i - 1] + triangle[i][i];
            }
            return *min_element(f[(n - 1) % 2].begin(), f[(n - 1) % 2].end());
        }
    };
    
    
    > 作者:LeetCode-Solution
    > 链接:https://leetcode-cn.com/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
    > 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
    

    上述方法的空间复杂度为O(n),使用了2n 的空间存储状态。我们还可以继续进行优化吗?

    答案是可以的。我们从 i到 0 递减地枚举 j,这样我们只需要一个长度为 n 的一维数组 f,就可以完成状态转移。

    这样虽然空间复杂度仍然为 O(n),但我们只使用了 n 的空间存储状态,减少了一半的空间消耗。

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
            vector<int> f(n);
            f[0] = triangle[0][0];
            for (int i = 1; i < n; ++i) {
                f[i] = f[i - 1] + triangle[i][i];
                for (int j = i - 1; j > 0; --j) {
                    f[j] = min(f[j - 1], f[j]) + triangle[i][j];
                }
                f[0] += triangle[i][0];
            }
            return *min_element(f.begin(), f.end());
        }
    };
    
    
    > 作者:LeetCode-Solution
    > 链接:https://leetcode-cn.com/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
    > 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
    

    复杂度分析

    时间复杂度:O(n^2),其中 n 是三角形的行数。
    
    空间复杂度:O(n)。
    
    更多相关内容
  • 针对障碍物分布复杂、存在封闭边界的受限空间, 提出一种环境自适应区域栅格化的优化路径规划算 法. 该算法首先将环境自适应划分为区域栅格, 并提出阻碍度指标降低搜索空间的维度以优化区域栅格的划分; 然 ...
  • 为提高足式移动机器人的避障能力...然后,结合经典的A*算法,建立机器人局部世界坐标系、机器人质心轨迹转换模型、碰撞模型启发式代价函数,在全局环境中寻找最优成本最小路径;最后,通过仿真实验验证该算法的有效性.
  • 最小路径和 题目 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 ...

    最小路径和

    题目

    给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

    说明:每次只能向下或者向右移动一步。

    示例

    输入:

    [
    [1,3,1],
    [1,5,1],
    [4,2,1]
    ]

    输出: 7

    解释: 因为路径 1→3→1→1→1 的总和最小。

    解题

    分析

    这道题,我能想到的一共三种解法。

    首先,这很类似与迷宫的问题,很显然可以使用递归来解决,我们可以把所有可能到达右下角最后一个元素的路线的权值和都计算出来,然后取最小的一个。可以优化在递归的过程中,就记录最小值,某条路径递归的一半就比这个最小值大或者小,那么我们就终止递归。

    这种方式的时间复杂度为O(2^m+n),空间复杂度为为O(m+n)


    第二种,这道题很显然是一个动态规划的问题,到达最后一个元素(n,m)的最短路径,要取决于到达(n - 1,m)和(n,m - 1)的元素的最短路径,如果要求不破坏原有的数据,我们可以再定义一个同样大小的二维数组,从最后一行开始,从后往前遍历所有的元素,每一个元素都记录右下角到这个节点的最短路径,最后返回(0,0)个元素就可以了。(一维数组也可以实现)

    这种方式的时间复杂度为O(mn),空间复杂度为为O(mn)(一维数组的话空间复杂度为O(m))


    如果不需要保留原来的数据结构,我们可以在题目中的二维数组直接修改,这样空间复杂度为O(1)

    代码

    第一种-递归优化版本

    class Solution {
        
        // 记录当前的最小值
        int min = -1;
        
        public int minPathSum(int[][] grid) {
            recursive(grid, 0, 0, grid[0][0]);
            return min;
        }
        
        private void recursive(int[][] grid, int i, int j, int sum) {
    
            // 中断递归的条件,否则会超时
            if (min != -1 && sum >= min) {
                return;
            }
    
            if (i == grid.length - 1 && j == grid[0].length - 1) {
                min = sum;
                return;
            }
    
            // 优先向下走
            if (i < grid.length - 1) {
                recursive(grid, i + 1, j, sum + grid[i + 1][j]);
            }
    
            // 上路走不通再向下走
            if (j < grid[0].length - 1) {
                recursive(grid, i, j + 1, sum + grid[i][j + 1]);
            }
        }
    }
    

    第二种-二维数组动态规划

    class Solution {
        
        public int minPathSum(int[][] grid) {
            int[][] dp = new int[grid.length][grid[0].length];
    
            for (int i = grid.length - 1; i >= 0; i--) {
                for (int j = grid[0].length - 1; j >= 0; j--) {
    
                    if (i < grid.length - 1 && j < grid[0].length - 1) {
                        dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
                    } else if (i == grid.length - 1 && j < grid[0].length - 1) {
                        dp[i][j] = dp[i][j + 1] + grid[i][j];
                    } else if (i < grid.length - 1 && j == grid[0].length - 1) {
                        dp[i][j] = dp[i + 1][j] + grid[i][j];
                    } else {
                        dp[i][j] = grid[i][j];
                    }
                }
            }
    
            return dp[0][0];
        }
        
    }
    

    第三种-动态规划-原地修改

    class Solution {
        
        public int minPathSum(int[][] grid) {
            for (int i = grid.length - 1; i >= 0; i--) {
                for (int j = grid[0].length - 1; j >= 0; j--) {
    
                    if (i < grid.length - 1 && j < grid[0].length - 1) {
                        grid[i][j] = Math.min(grid[i + 1][j], grid[i][j + 1]) + grid[i][j];
                    } else if (i == grid.length - 1 && j < grid[0].length - 1) {
                        grid[i][j] = grid[i][j + 1] + grid[i][j];
                    } else if (i < grid.length - 1 && j == grid[0].length - 1) {
                        grid[i][j] = grid[i + 1][j] + grid[i][j];
                    }
    
                }
            }
    
            return grid[0][0];
        }
        
    }
    

    leetcode展示

    在这里插入图片描述

    展开全文
  • 最小路径和 提示: m == grid.length n == grid[i].length 1 <= m, n <= 200 0 <= grid[i][j] <= 100 题解 方法一:递归解法(超时) right 表示当前向已右走的步数,down 表示当前已向下走的步数,...

    题目

    leetcode 64. 最小路径和
    在这里插入图片描述
    提示:

    • m == grid.length
    • n == grid[i].length
    • 1 <= m, n <= 200
    • 0 <= grid[i][j] <= 100

    题解

    方法一:递归解法(超时)

    right 表示当前向已右走的步数,down 表示当前已向下走的步数,cur 表示当前走过的路径和。

    此方法超时,应该使用 (方法二)动态规划解法。

    public static int minPathSum1(int[][] grid) {
        int right = 0, down = 0;
        return getMinSum(0, right, down, grid);
    }
    
    public static int getMinSum(int cur, int right, int down, int[][] grid) {
        int m = grid.length - 1; // 行边界
        int n = grid[0].length - 1; // 列边界
    
        cur += grid[down][right];
        if (right == n && down == m) { // 到终点
            return cur;
        } else if (right == n) { // 右边界
            return getMinSum(cur, right, down + 1, grid);
        } else if (down == m) { // 下边界
            return getMinSum(cur, right + 1, down, grid);
        } else {
            return Math.min(getMinSum(cur, right, down + 1, grid), getMinSum(cur, right + 1, down, grid));
        }
    }
    

    方法二:动态规划

    由于路径的方向只能是向下或向右,因此网格的第一行的每个元素只能从左上角元素开始向右移动到达,网格的第一列的每个元素只能从左上角元素开始向下移动到达,此时的路径是唯一的,因此每个元素对应的最小路径和即为对应的路径上的数字总和。

    对于不在第一行和第一列的元素,可以从其上方相邻元素向下移动一步到达,或者从其左方相邻元素向右移动一步到达,元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关,因此可以使用动态规划求解。

    创建二维数组 dp,与原始网格的大小相同,dp[i][j] 表示从左上角出发到 (i,j) 位置的最小路径和。显然,dp[0][0]=grid[0][0]。对于 dp 中的其余元素,通过以下状态转移方程计算元素值。

    状态转移方程:

    • 当 i>0 且 j=0 时,dp[i][0] = dp[i-1][0] + grid[i][0]

    • 当 i=0 且 j>0 时,dp[0][j] = dp[0][j-1] + grid[0][j]

    • 当 i>0 且 j>0 时,dp[i][j] = min(dp[i−1][j],dp[i][j−1]) + grid[i][j]

    最后得到 dp[m-1][n-1] 的值,即为从网格左上角到网格右下角的最小路径和。

    代码

    public static int minPathSum2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) { // 计算最左列的值:此时左边是边界
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) { // 计算最上行的值:此时上边是边界
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) { // 其余元素
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
    

    复杂度分析

    • 时间复杂度:O(m*n),其中 m 和 n 分别是网格的行数和列数。需要对整个网格遍历一次,计算 dp 的每个元素的值。

    • 空间复杂度:O(m*n),其中 m 和 n 分别是网格的行数和列数。创建一个二维数组 dpdp,和网格大小相同。
      注:空间复杂度可以优化,例如每次只存储上一行的 dp 值,则可以将空间复杂度优化到 O(n)。

    附:4*4矩阵的16步完整过程示例

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    附:完整代码(含测试用例)

    class Solution {
        public static void main(String[] args) {
    //        int[][] grid = {{1, 2, 3}, {4, 5, 6}};
            int[][] grid = {{3, 8, 6, 0, 5, 9, 9, 6, 3, 4, 0, 5, 7, 3, 9, 3}, {0, 9, 2, 5, 5, 4, 9, 1, 4, 6, 9, 5, 6, 7, 3, 2}, {8, 2, 2, 3, 3, 3, 1, 6, 9, 1, 1, 6, 6, 2, 1, 9}, {1, 3, 6, 9, 9, 5, 0, 3, 4, 9, 1, 0, 9, 6, 2, 7}, {8, 6, 2, 2, 1, 3, 0, 0, 7, 2, 7, 5, 4, 8, 4, 8}, {4, 1, 9, 5, 8, 9, 9, 2, 0, 2, 5, 1, 8, 7, 0, 9}, {6, 2, 1, 7, 8, 1, 8, 5, 5, 7, 0, 2, 5, 7, 2, 1}, {8, 1, 7, 6, 2, 8, 1, 2, 2, 6, 4, 0, 5, 4, 1, 3}, {9, 2, 1, 7, 6, 1, 4, 3, 8, 6, 5, 5, 3, 9, 7, 3}, {0, 6, 0, 2, 4, 3, 7, 6, 1, 3, 8, 6, 9, 0, 0, 8}, {4, 3, 7, 2, 4, 3, 6, 4, 0, 3, 9, 5, 3, 6, 9, 3}, {2, 1, 8, 8, 4, 5, 6, 5, 8, 7, 3, 7, 7, 5, 8, 3}, {0, 7, 6, 6, 1, 2, 0, 3, 5, 0, 8, 0, 8, 7, 4, 3}, {0, 4, 3, 4, 9, 0, 1, 9, 7, 7, 8, 6, 4, 6, 9, 5}, {6, 5, 1, 9, 9, 2, 2, 7, 4, 2, 7, 2, 2, 3, 7, 2}, {7, 1, 9, 6, 1, 2, 7, 0, 9, 6, 6, 4, 4, 5, 1, 0}, {3, 4, 9, 2, 8, 3, 1, 2, 6, 9, 7, 0, 2, 4, 2, 0}, {5, 1, 8, 8, 4, 6, 8, 5, 2, 4, 1, 6, 2, 2, 9, 7}};
            System.out.println(minPathSum1(grid));
            System.out.println(minPathSum2(grid));
        }
    
        /**
         * 递归解法(超时)
         */
        public static int minPathSum1(int[][] grid) {
            int right = 0, down = 0;
            return getMinSum(0, right, down, grid);
        }
    
        public static int getMinSum(int cur, int right, int down, int[][] grid) {
            int m = grid.length - 1; // 行边界
            int n = grid[0].length - 1; // 列边界
    
            cur += grid[down][right];
            if (right == n && down == m) { // 到终点
                return cur;
            } else if (right == n) { // 右边界
                return getMinSum(cur, right, down + 1, grid);
            } else if (down == m) { // 下边界
                return getMinSum(cur, right + 1, down, grid);
            } else {
                return Math.min(getMinSum(cur, right, down + 1, grid), getMinSum(cur, right + 1, down, grid));
            }
        }
    
        /**
         * 动态规划解法(推荐)
         */
        public static int minPathSum2(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            int rows = grid.length, columns = grid[0].length;
            int[][] dp = new int[rows][columns];
            dp[0][0] = grid[0][0];
            for (int i = 1; i < rows; i++) { // 计算最左列的值:此时左边是边界
                dp[i][0] = dp[i - 1][0] + grid[i][0];
            }
            for (int j = 1; j < columns; j++) { // 计算最上行的值:此时上边是边界
                dp[0][j] = dp[0][j - 1] + grid[0][j];
            }
            for (int i = 1; i < rows; i++) { // 其余元素
                for (int j = 1; j < columns; j++) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
            return dp[rows - 1][columns - 1];
        }
    }
    
    展开全文
  • [DP题解]矩阵最小路径和问题

    千次阅读 2019-03-16 18:48:43
    [DP题解]矩阵最小路径和问题 【题目】给定一个矩阵,例如demo,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径,返回所有的路径中最小的路径。 算法分析: ...

    [DP题解]矩阵最小路径和问题

    【题目】给定一个矩阵,例如demo,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,路径上所有的数字累加起来就是路径和,返回所有的路径和中最小的路径和。

    算法分析:

    这是一个典型的动态规划算法问题。

    分析如下:

    例如下图中的矩阵demo,1-3-1-0-6-1-0 的路径和最小,值为12.

    再看:

    例如:

    由此进行算法设计:

     注意:下面代码中的矩阵是通过随机数生成的。(与分析过程中的实例矩阵数值不同)

    package com.bean.algorithmexec;
    
    public class MatrixPath {
    	/*
    	 * 给定一个矩阵m,从左上角开始每次只能向右或者向下走,最后到达右下角的位置,
    	 * 路径上所有的数字累加起来就是路径和,返回所有的路径中最小的路径和。
    	 * 例如:
    	 * 1 3 5 9 
    	 * 8 1 3 4 
    	 * 5 0 6 1
    	 * 8 8 4 0
    	 * 路径 1,3,1, 0,6,1,0 是所有路径中路径和最小的,所以返回12。
    	 * */
    
    	/*
    	 * 计算方法
    	 * */
    	
    	public static int minPathSum(int [][] m) {
    		
    		if(m==null || m.length==0 || m[0]==null || m[0].length ==0) {
    			return 0;
    		}
    		
    		int row=m.length;
    		int col=m[0].length;
    		int[][] dp=new int[row][col];
    		dp[0][0] = m[0][0];
    		
    		for(int i=1;i<row;i++) {
    			dp[i][0] = dp[i-1][0]+m[i][0];
    		}
    		
    		for(int j=1;j<col;j++) {
    			dp[0][j] = dp[0][j-1]+m[0][j];
    		}
    		
    		for(int i=1;i<row;i++) {
    			for(int j=1;j<col;j++) {
    				dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];
    			}
    		}
    				
    		return dp[row-1][col-1];
    	}
    	
    	
    	/*
    	 * 创建一个 M*N的矩阵,并赋予行和列随机整数值,元素的取值范围在1-10之间。
    	 * */
    	
    	public static int[][] createMatrix(int m, int n) {
    		
    		int [][] matrix=new int[m][n];
    		int seed=0;
    		for(int i=0;i<m;i++) {
    			for(int j=0;j<n;j++) {
    				seed=(int) ((Math.random()*10)+1);
    				matrix[i][j]=seed;
    			}
    		}
    		
    		return matrix;
    	}
    	
    	
    	/*
    	 * 输出矩阵 
    	 * */
    	public static void printMatrix(int[][] matrix) {
    		for(int i=0;i<matrix.length;i++) {
    			for(int j=0;j<matrix[0].length;j++) {
    				System.out.print(matrix[i][j]+"\t");
    			}
    			System.out.println();
    		}
    	}
    	
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		int[][] matrix=createMatrix(4,4);
    		printMatrix(matrix);
    		
    		int sum=minPathSum(matrix);
    		
    		System.out.println("sum = "+sum);
    		
    	}
    
    }
    

    输出结果为:

    结果可以自己来分析~

    6	9	4	10	
    5	4	6	3	
    1	3	5	7	
    9	6	4	3	
    sum = 27

    上面的算法设计中,矩阵一共有M*N个位置,每个位置都计算一次从(0,0)位置到达自己的最小路径和,计算的时候只是比较上边位置的最小路径与左边位置的最小路径和哪个更小,所以时间复杂度为O(M*N),dp矩阵的大小为M*N,所以额外空间复杂度为O(M*N)。


    动态规划算法

    public static int minPathSum(int [][] m) {
    		
    		if(m==null || m.length==0 || m[0]==null || m[0].length ==0) {
    			return 0;
    		}
    		
    		int row=m.length;
    		int col=m[0].length;
    		int[][] dp=new int[row][col];
    		dp[0][0] = m[0][0];
    		
    		for(int i=1;i<row;i++) {
    			dp[i][0] = dp[i-1][0]+m[i][0];
    		}
    		
    		for(int j=1;j<col;j++) {
    			dp[0][j] = dp[0][j-1]+m[0][j];
    		}
    		
    		for(int i=1;i<row;i++) {
    			for(int j=1;j<col;j++) {
    				dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])+m[i][j];
    			}
    		}
    				
    		return dp[row-1][col-1];
    }

    LeetCode提交之后,Accepted!

     


    上面的DP算法过程还可以在进一步进行优化。

    后续补充。

     

    展开全文
  • 使用自由空间和 COST231 模型估计路径损耗。 提供信号强度的估计图。 这是一种 2D 视线方法,它考虑了发射器接收器之间的单独墙壁。 COST231 类似于 Motley-Keenan。 仅使用蓝图图像即可为每面墙分配不同的衰减...
  • 将完整切割环上旋转轴运动最低总耗能作为优化目标,通过Dijkstra最小路径优化算法,获得完整切割环上的最佳切割方式。通过实例分析,该方法可避免BC轴瞬间摆动过大情况,提高了切割头运动的平顺性。
  • 三角形的最小路径和(动态规划)

    千次阅读 2019-04-18 10:33:52
    题目如下: ...那么最小路径和肯定是取2 3的,即最小路径和为5。现在我们假设到了第i行,从第一行到第i-1行的最小路径和我们已经知道,这里要声明的一点是,最小路径和与其最后一行的出口是对应的,...
  • 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为&amp;nbsp;11(即,2&...
  • 从左上角到右下角路径数 LeetCode 62 动态规划法 class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < n; i++) dp[0][i] = 1; for (int i = 0; i &...
  • 在成本距离方面,成本路径工具可生成用于记录最小成本路径或从所选位置到累积成本面内所定义的最近源像元之间的路径的输出栅格。
  • 本文以某 SUV 车型为研究对象,建立车辆在低速时的运动学模型,通过逆 向路径规划分析平行泊车垂直泊车过程中可能发生的碰撞点,计算...采用多步入库的方式,汽车能在更小的空间内完成泊车,泊车路径更合理安 全。
  • 路径规划之基于优化的规划算法

    千次阅读 2022-03-27 21:35:07
    Ren等人针对势场法存在振荡等问题,将改进牛顿法优化方法应用于连续势场导航模型,并考虑了机器人非全向约束移动障碍物影响,极大提升了系统性能,但存在优化计算成本较高的问题[13]。 Ratliff等人针对高维运动...
  • 路径规划与优化学习系列,人生之路在于不断规划和优化,无人机飞行之路也是如此
  • LeetCode 64最小路径和

    千次阅读 2018-09-17 21:48:59
    网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入: [ &nbsp; [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的...
  • 路径优化搜素算法

    万次阅读 多人点赞 2018-11-26 11:42:19
    B、对于每一个不属于集合 T 的点,比如顶点 q, 查看新加入的顶点 r 是否可以直接到达顶点 q,如果是,则比较通过顶点 r 到达顶点 q 的路径长度当前的dist[q]值,然后取较小值,即 dist[q] := min(dist[r]+W(r, q)...
  • 动态规划--矩阵最小路径和

    千次阅读 2017-05-27 20:03:39
    题目描述:给定一个 N*M 的矩阵arr,从左上角开始每次只能向下或者向右走,最后到达右下角。路径上所有点的数字为 路径,求...dp[i][j] 表示 达到点 arr[i][j] 是的最小路径和,因为每次只能向下或者向右,所以要达
  • 图论-路径优化算法总结

    千次阅读 2020-12-30 21:15:48
    目录 1:Dijkstra算法 1.1:算法思想 1.2:算法步骤 1.3:代码演示 ...迪杰斯特拉(Dijkstra)算法是典型的最短路径的算法,用来求得从起始点到其他所有点最短路径(单源最短路径)。该算法采用了贪心的思想
  • 最小生成树、最短路径

    千次阅读 2020-09-21 10:19:40
    最小生成树 在图论中,无向图 G 的生成树(英语:Spanning Tree)是具有 G 的全部顶点,但边数最少的连通子图。[1] 一个图的生成树可能有多个。 带权图的生成树中,总权重最小的称为最小生成树。 它在实际中有什么...
  • 64、最小路径和 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ...
  • 1. 引言VRP问题指车辆路线优化问题,一般而言,有一个或多个供应点,多个需求点有不同的货物需求,分析如何组织货车在这些需求点中进行配送从而达到总里程最小、配送时间最短、总成本最低等目标。VRP问题普遍被认为...
  • 三角形最小路径和前言一、自底向上方法1:动态规划(DP)方法2:递归二、自顶向下 如果你从本文中学习到丝毫知识,那么请您点点关注、点赞、评论收藏 大家好,我是爱做梦的鱼,我是东北大学大数据实验班大三的小...
  • LeetCode-64-Minimum Path Sum最小路径和问题 题目大意 递归尝试版本 记忆化搜索 二维空间dp表 滚动数组优化空间O(min{N,M}) 打印解 题目链接 题目大意 给定一个包含非负整数的 m x n 网格,请找出一条从...
  • 通过最小化成本函数,可以使积分变量复杂化,并在复杂空间优化积分路径,这反映了符号问题的严重性。 为了准备和优化多维系统中的积分路径,我们利用了前馈神经网络。 我们以有限化学势下的二维复数理论为例,...
  • 本题属于最小路径问题的简化版原题地址初入门算法的同学见到这题可能会有些懵,首先会想到遍历去寻找每一个点的最优路径,这个思路是没有问题的但是如何实现的?本类问题相似的还有背包客问题、网络流优化等问题,...
  • 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。 说明:...
  • 路径规划-Minimum snap轨迹优化

    千次阅读 2021-03-08 08:43:33
    传统的路径规划pipeline包括路径搜索轨迹优化两部分。 轨迹优化的目的是生成光滑轨迹,其必要性如下: 适合移动机器人的自主移动 速度加速度等动力学状态无法突变 移动机器人不必在拐角处加速减速 节约能量 ...
  • 研究了考虑碳排放速度优化的带时间窗车辆路径问题,引入了基于速度的碳排放计算方法,以油耗、碳排旅行时间费用最小化为目标,将速度作为决策变量,建立了混合整数规划模型...
  • 针对路径跟踪过程中,因车辆转向系统转角转速约束、车辆最小转弯半径约束、车辆行驶速度等因素导致的车辆偏离目标路径现象,提出结合过定点控制的路径跟踪控制方法,设计出非时间参考的车辆过定点控制律,并通过 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 85,268
精华内容 34,107
关键字:

最小路径和 空间优化