作為一個拖延癥懶癌患者，外加年久失修，基礎(chǔ)不牢，我決定每天做一題，堅(jiān)持打卡，今天是我第一天，希望自己可以堅(jiān)持下來。
Given amxn grid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
Note:You can only move either down or right at any point in time.
題目大意大致為有這樣一個數(shù)組，數(shù)組里都有對應(yīng)的值，可以向下走或者向右走，最后返回?cái)?shù)值最小的路徑，可以理解為一個動態(tài)規(guī)劃的問題。
動態(tài)規(guī)劃：（這是第一次做動態(tài)規(guī)劃方面的題目，也不想搞ACM競賽之類，只是想積累經(jīng)驗(yàn)）
摘自知乎 作者：端澤
先談動態(tài)規(guī)劃的意義——望文生義，“動態(tài)”規(guī)劃對應(yīng)“動態(tài)”的問題：你并不知道問題的規(guī)模會有多大，而不論是個位數(shù)還是百萬級，都能以較快速度(動態(tài)規(guī)劃是一種泛用性算法，而泛用性算法與特定算法相比往往存在性能差距)將結(jié)果正確計(jì)算出來。這是對于計(jì)算機(jī)科學(xué)最直觀的意義，當(dāng)然我認(rèn)為其對人生亦有一定指導(dǎo)意義，但那是見仁見智的事了。
動態(tài)規(guī)劃這一思想的實(shí)質(zhì)其實(shí)是以下兩點(diǎn)：
1.分析問題，構(gòu)造狀態(tài)轉(zhuǎn)移方程
2.以空間換時(shí)間
讓我們結(jié)合一個簡單例子來理解一下：
以乘法計(jì)算為例，乘法的定義其實(shí)是做n次加法，請先忘掉九九乘法表，讓你計(jì)算9*9，如何得到81這個解？計(jì)算9*10呢？9*999……以及9*n呢？
1.分析問題，構(gòu)造狀態(tài)轉(zhuǎn)移方程
“狀態(tài)轉(zhuǎn)移方程”的學(xué)術(shù)定義亦可簡單找到（比如置頂答案），略去不表。光看“方程”二字，可以明白它是一個式子。
針對以上問題，我們構(gòu)造它的狀態(tài)轉(zhuǎn)移方程。
問題規(guī)模小的時(shí)候，我們可以容易得到以下式子：
9*0=0；
9*1=0+9；
9*2=0+9+9；
……
可以得到：9*n=0+9+...+9(總共加了n個9)。嚴(yán)謹(jǐn)?shù)淖C明可以使用數(shù)學(xué)歸納法，略去不表。
現(xiàn)在，定義dp(n)=9*n,改寫以上式子：
dp(0)=9*0=0；
dp(1)=9*1=dp(0)+9；
dp(2)=9*2=dp(1)+9；
……
作差易得：dp(n)=dp(n-1)+9；這就是狀態(tài)轉(zhuǎn)移方程了。
可以看到，有了狀態(tài)轉(zhuǎn)移方程，我們現(xiàn)在可以順利求解9*n（n為任意正整數(shù)）這一問題。
2.以空間換時(shí)間
雖然能解，但當(dāng)n很大時(shí)，計(jì)算耗時(shí)過大，看不出狀態(tài)轉(zhuǎn)移方程dp(n)=dp(n-1)+9與普通方程9*n=0+9+...+9(總共加了n個9)相比沒有任何優(yōu)勢。
這時(shí)，如果dp(n-1)的結(jié)果已知，dp(n)=dp(n-1)+9只需計(jì)算一次加法，而9*n=0+9+...+9(總共加了n個9)則需計(jì)算n-1次加法，效率差異一望即知。
存儲計(jì)算結(jié)果，可令狀態(tài)轉(zhuǎn)移方程加速，而對普通方程沒有意義。
以空間換時(shí)間，是令動態(tài)規(guī)劃具有實(shí)用價(jià)值的必備舉措。
總之，根據(jù)我的理解，我覺得這個很像小時(shí)候做的找規(guī)律的題目，第n個數(shù)需要靠之前的來得到，因此，叫做動態(tài)規(guī)劃，也就是dp。
接下來要看這道題了，假如我有一個矩陣grid：
1 2 3 4
5 9 9 0
1 8 4 3
我得到一個新的矩陣，result記錄著gird里面到達(dá)每一個元素的最小值，這樣最后一個元素也就是我們所要求的值，就是到他的最小值，因此，
result[0][0] = gird[0][0]
result[0][j] = result[0][j-1]+gird[0][j]
result[i][0] = result[]i-1[0]+gird[i][0]
result[i][j] = min(result[i - 1][j], result[i][j - 1])+gird[i][j]
接下來就是算法的實(shí)現(xiàn)了：
結(jié)束......
joker
