Minimum Path Sum, Leetcode 解题笔记

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.


public class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] store = new int[n];
        //initialize the first row
        store[0] = grid[0][0];
        for(int i = 1; i < n; i++){
            store[i] = grid[0][i] + store[i-1];
        for(int i = 1; i < m; i++){
            //initialize the first element of each row
            store[0] = store[0] + grid[i][0];
            for(int j = 1; j < n; j++){
                store[j] = grid[i][j] + Math.min(store[j], store[j-1]);
        return store[n-1];

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s