小猴进入了一个由 n×n 个格子组成的地区,每个格子都可以走。 第 i 行第 j 列的格子里有 vi,j 个金币。 小猴从地图的左上角(第1行第1列)出发,每次只能向下走或向右走,并且收集路上经过的格子的金币。(起点和终点也算经过的格子)。
这次小猴拥有两个钱袋,每次经过一个格子时,小猴可以选择收集这个格子中的金币,并将金币全部装入两个钱袋中的一个(小猴不能将金币分别装入两个袋子);也可以放弃这个格子中的金币。到达右下角(第 n 行第 n 列)时,他必须在两个钱袋里装同样数量的金币,才能带着金币离开这个地区。
问小猴到达右下角(第 n行第 n 列)时,最多能带走多少金币?