這道題之前一直郁悶在如何求這個(gè)動(dòng)態(tài)規(guī)劃式上面了,我一直按照的是常規(guī)的思路,我是這么想的,map[n][m]=map[n-1][m-1]+r1 或map[n][m]=map[n-1][m]+r2 或
map[n][m]=map[n][m-1]+r2 ,但是這樣想不出 子問(wèn)題,,于是郁悶了,,沒(méi)想到,這個(gè)題目其實(shí)思路可以打開(kāi)的,,如果我們按照這樣思考,因?yàn)樽疃痰穆穭牛褪俏覀冏咦疃嗟慕輳降穆?,如果把最多捷徑的條求出來(lái)了,那么最短路徑也就求出來(lái)了,這樣的話(huà),因?yàn)樽哌^(guò)捷徑的話(huà),橫,縱坐標(biāo)都是增加的,那么我們只需要按照 捷徑的坐標(biāo)進(jìn)行規(guī)則排序,那么最后到達(dá)每一個(gè)捷徑點(diǎn)的最多捷徑數(shù)就可以求出來(lái)。。。
總這一題給自己的啟示是,想問(wèn)題的時(shí)候思路要打開(kāi),這條路不行,就換一條,多換幾個(gè)思路也許就能巧妙的解決,而思考的魅力就在于此!