這道題之前一直郁悶在如何求這個(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 ,但是這樣想不出 子問題,,于是郁悶了,,沒想到,這個(gè)題目其實(shí)思路可以打開的,,如果我們按照這樣思考,因?yàn)樽疃痰穆穭牛褪俏覀冏咦疃嗟慕輳降穆罚绻炎疃嘟輳降臈l求出來了,那么最短路徑也就求出來了,這樣的話,因?yàn)樽哌^捷徑的話,橫,縱坐標(biāo)都是增加的,那么我們只需要按照 捷徑的坐標(biāo)進(jìn)行規(guī)則排序,那么最后到達(dá)每一個(gè)捷徑點(diǎn)的最多捷徑數(shù)就可以求出來。。。
總這一題給自己的啟示是,想問題的時(shí)候思路要打開,這條路不行,就換一條,多換幾個(gè)思路也許就能巧妙的解決,而思考的魅力就在于此!