題目連結(jié)：
題目大意：
第一列給定兩正整數(shù) m 、 n （1 ≦ m ≦ 50 ， 1 ≦ n ≦ 10000），代表有一個(gè) m × n 的網(wǎng)格地圖。接著有 m 列，每列給定 n 個(gè)整數(shù)（皆介於 -100 ～ 100 之間），代表每格所擁有的經(jīng)驗(yàn)值。
勇者從地圖第一列任意位置開(kāi)始，每次可以往左、往右或是往下走一格（第一列在上方、第 m 列在下方），但是不能走到重複的格子。試問(wèn)勇者從第一列走到第 m 列時(shí)最多可以獲得多少經(jīng)驗(yàn)值？
範(fàn)例輸入：
1 5
2 1 4 -7 4
範(fàn)例輸出：
7
解題思維：
定義 T[i][j] 為第 i 列第 j 行這個(gè)格子的經(jīng)驗(yàn)值、 D[i][j][k] 為第 i 列第 j 行從方向 k 走過(guò)來(lái)可以形成的最大值，其中 1 ≦ i ≦ m ， 1 ≦ j ≦ n ， k = 0（上方）、 1（左方）或是 2（右方）。
接著再定義 D[0][j][k] 對(duì)於任意 (j, k) 值以及 D[i][0][k] 、 D[i][n + 1][k] 對(duì)於任意 (i, k) 值皆預(yù)設(shè)值為 0 。（可以視為把 m × n 的地圖用一圈 0 包起來(lái)（除了最下面））
因此，可以看到對(duì)於位置 (i, j) ，D[i][j][k] 的遞迴式如下：
D[i][j][0] = T[i][j] + max(D[i-1][j][0], D[i-1][j][1], D[i-1][j][2])
因?yàn)榉较?0 代表從上方來(lái)，所以就看上面一格的最大值加上本格的經(jīng)驗(yàn)值。
D[i][j][1] = T[i][j] + max(D[i][j-1][0], D[i][j-1][1])
因?yàn)榉较?1 代表從左方來(lái)，所以就看左邊一格的最大值加上本格的經(jīng)驗(yàn)值，但是要忽略 D[i-1][j-1][2]，因?yàn)樵撝凳菑谋靖衽苓^(guò)去而產(chǎn)生，如果考慮進(jìn)來(lái)則會(huì)走回頭路。
D[i][j][2] = T[i][j] + max(D[i][j+1][0], D[i][j+1][2])
因?yàn)榉较?2 代表從右方來(lái)，所以就看右邊一格的最大值加上本格的經(jīng)驗(yàn)值，但是要忽略 D[i-1][j+1][1]，理由同上。
因此我們就從第一列開(kāi)始，對(duì)於每一列從左到右掃過(guò)求出 D[i][j][0] 以及 D[i][j][1]。然後再?gòu)挠业阶髵哌^(guò)，求出 D[i][j][2]。
而所求就是最後一列 D[m][j][k] 之值最大的。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
