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.

与前一题思路一样,还是一维DP,不过这次数组中存的是当前位置的最小路径,也就是更新当前位置的元素时要加合上面和左边中较小的数字。注意边界处理要细心。

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];
    }
}
Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s