【经典算法】LeetCode 64. 最小路径和(Java/C/Python3/Golang实现含注释说明,Easy)

作者主页： 🔗进朱者赤的博客

精选专栏：🔗经典算法

作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞

————————————————-

文章目录

• 题目描述
• 思路及实现
• • 方式一：动态规划（朴素DP ）
  • • 思路
    • 代码实现
    • • Java版本
      • C语言版本
      • Python3版本
      • go
      • 复杂度分析
      • 方式二：滚动数组优化DP
      • • 思路
        • 代码实现
        • • Java版本
          • C语言版本
          • Python3版本
          • go
          • 复杂度分析
          • 总结
          • 相似题目
            • 标签(题目类型)：动态规划

              题目描述

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

              

              说明：每次只能向下或者向右移动一步。
               
              示例 1：
              输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
              输出：7
              解释：因为路径 1→3→1→1→1 的总和最小。
              示例 2：
              输入：grid = [[1,2,3],[4,5,6]]
              输出：12
               
              提示：
              m == grid.length
              n == grid[i].length
              1 
                  public int minPathSum(int[][] grid) {
                      if (grid == null || grid.length == 0 || grid[0].length == 0) {
                          return 0;
                      }
                      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