【題目描述】
Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
給定一個(gè)只含非負(fù)整數(shù)的m*n網(wǎng)格缤苫，找到一條從左上角到右下角的可以使數(shù)字和最小的路徑杖们。
【注】：你在同一時(shí)間只能向下或者向右移動(dòng)一步
【題目鏈接】
www.lintcode.com/en/problem/minimum-path-sum/
【題目解析】
本題是動(dòng)態(tài)規(guī)劃基本的基本類(lèi)型艇抠。該題的思想是建立f[i][j]术羔，表示從起點(diǎn)到f[i][j]最小權(quán)值屁柏。
由于(i,j)只能由(i-1,j)和(i,j-1)兩個(gè)點(diǎn)到達(dá)，假設(shè)我們已經(jīng)知道了f[i-1][j]和f[i][j-1]，則f[i][j]的最小值等于min(f[i-1][j], f[i][j - 1])加上當(dāng)前(i,j)的權(quán)值，即：
f[i][j] = g[i][j] + min(f[i - 1][j], f[i][j - 1])
所以我們通過(guò)行列的遞推沾瓦，就能夠得到從左上角到右下角的最小權(quán)值f[m][n]，時(shí)間復(fù)雜度為O(mn)谦炒。
【參考答案】
