java动态规划贪吃蛇

Question

给定一个金币地图，地图上的数值代表金币的数量。

此时地图上方有一只贪吃蛇从任意一点进入，每经过一处就会吞噬此处的金币。最终从地图下方出去。

贪吃蛇每次只会向下走，且不能走直线，也就是说，如果它在吞噬了地图中第 a 行第 b 列的 金币后，下一次只能走向第 a + 1行的第 c列（c != b）

求：该贪吃蛇能吞噬的最大金币数是多少。
一个 m x n 的地图 a

1 ≤ m, n≤ 3000

1 ≤ai≤ 100