Minimum path sum@leetcode

微博：http://www.weibo.com/cathyhwzn

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions

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.

» Solve this problem

This is a typical dynamic programing problem. It's almost the same kind as unique path.

It's two dimensional dp. But we can use one dimensional array to handle it. We define an array dp here.

First of all, we gotta to figure out the pattern of the problem here, which is f(i,j) = min{f(i-1,j), f(i, j-1)} + x_i,j. f(i,j) means the smallest path sum for reaching position (i,j).

Second, we put this formula in code. Thus we have dp[j] = min{dp[j], dp[j-1]} + gride[i][j-1].