64.Minimum-Path-Sum

64. Minimum Path Sum

题目地址

https://leetcode.com/problems/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.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

代码

Approach 1: DFS - bottom up

Complexity Analysis

• Time complexity : O(2^(_m+_n)). For every move, we have atmost 2 options.

• Space complexity : O(m+n). Recursion of depth m+n.

class Solution {
    public int minPathSum(int[][] grid) {
      return calculate(grid, 0, 0);
    }

    private int calculate(int[][] grid, int i, int j) {
      if (i == grid.length || j == grid[0].length) {
        return Integer.MAX_VALUE; // over the boundary
      }

      if (i == grid.length - 1 && j == grid[0].length - 1) {
        return grid[i][j]; // reach the end
      }

      return grid[i][j] + Math.min(calculate(grid, i + 1, j), 
                                     calculate(grid, i, j + 1));
  }

}

Approach #2 DFS - top up

class Solution {
  public int minPathSum(int[][] grid) {
    if (grid == null || grid[0] == null) return 0;

    int r = grid.length - 1;
    int c = grid[0].length - 1;

    return dfs(grid, r, c);
  }

  private int dfs(int[][] grid, int r, int c) {
    if (r == 0 && c == 0)        return grid[0][0];

    if (r == 0) {
      return dfs(grid, r, c - 1) + grid[r][c];
    }

    if (c == 0) {
      return dfs(grid, r - 1, c) + grid[r][c];
    }

    return grid[r][c] + Math.min(dfs(grid, r - 1, c),
                                 dfs(grid, r, c - 1));
  }
}

Approach #3 DP

Complexity Analysis

• Time complexity : O(mn). We traverse the entire matrix once.

• Space complexity : O(mn). Another array of row size is used.

class Solution {
  public int minPathSum(int[][] grid) {
    if (grid == null || grid[0] == null) return 0;

    int R = grid.length;
    int C = grid[0].length;

    int[][] dp = new int[R][C];
    dp[0][0] = grid[0][0];
    for (int i = 1; i < R; i++) {
      dp[i][0] = grid[i][0] + dp[i - 1][0];
    }
    for (int i = 1; i < C; i++) {
      dp[0][i] = grid[0][i] + dp[0][i - 1];
    }

    for (int i = 1; i < R; i++) {
      for (int j = 1; j < C; j++) {
        dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
      }
    }

   return dp[R - 1][C - 1];
  }
}

Approach #4 Dynamic Programming 2D

public class Solution {
    public int minPathSum(int[][] grid) {
        int R = grid.length;
        int C = grid[0].length;
        int[][] dp = new int[R][C];
                // 从终点往起点走
        for (int i = R - 1; i >= 0; i--) {
            for (int j = C - 1; j >= 0; j--) {
                if (i == R - 1 && j != C - 1) {
                    dp[i][j] = grid[i][j] + dp[i][j + 1]; // 只能往右走
                } else if(j == C - 1 && i != R - 1) {
                    dp[i][j] = grid[i][j] + dp[i + 1][j]; // 只能往下走
                } else if(j != C - 1 && i != R - 1) {            // 往右 + 往下
                    dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);
                } else {    // 终点-终点的距离
                    dp[i][j] = grid[i][j];
                }
            }
        }
        return dp[0][0];
    }
}

Approach #5 Dynamic Programming 1D

Complexity Analysis

• Time complexity : O(mn). We traverse the entire matrix once.

• Space complexity : O(n). Another array of row size is used.

class Solution {
  public int minPathSum(int[][] grid) {
    int R = grid.length;
    int C = grid[0].length;
    int[] dp = new int[C];
    for (int i = R - 1; i >= 0; i--) {
      for (int j = C - 1; j >= 0; j--) {
         if (i == R - 1 && j != C - 1) {
           dp[j] = grid[i][j] +  dp[j + 1]; // 只能往右
         } else if (j == C - 1 && i != R - 1) {
           dp[j] = grid[i][j] + dp[j]; // 只能往下
         } else if (j != C - 1 && i != R - 1) {     // 往下 + 往右
           dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
         } else {    // 终点
            dp[j] = grid[i][j];
         }
      }
    }

    return dp[0];
  }
}

Approach #6 Dynamic Programming (Without Extra Space)

Complexity Analysis

• Time complexity : O(mn). We traverse the entire matrix once.

• Space complexity : O(1). No extra space is used.

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