APCS 2020-10 實作題第三題

問題連結：

　　https://zerojudge.tw/ShowProblem?problemid=f314

 

想法：

　　先計算第M層任何房間左右移動可獲得的最高經驗值，接著從第M-1層到第1層，

逐次計算任何房間左右移動可獲得的最高經驗值，但須加上該路線終點房間下方房間

可獲得的最高經驗值，算到最上層後選取最大值即為解答。

 

0	5	-2	1
13	-19	3	1
-21	17	-13	8
0	-20	6	19
原始陣列

首先計算第M層任意房間為起點，可以獲得的最高經驗值，並存在相應位置的DP陣列中

5	5	25	25
最高經驗值陣列(DP)

接著計算第M-1層，此時需要將下方房間的最大值加入考量

如(1,2),(左上角為 (1,1) )，其路線為(2,2)->(2,3)->(2,4)->(3,4)

40	40	35	36
29	12	37	34
16	37	20	33
5	5	25	25
最高經驗值陣列(DP)

得出最後陣列後，輸出第一層出現的最大值

 

　　Code: