share - 《GRIDWALKING》采访街

Question

我最近在 interviewstreet 尝试了问题 GRIDWALKING。我尽我所能，但仍然无法做到正确。我的意思是，我得到了正确的逻辑（DP和帕斯卡）并解决了N = 1（他们提供的样本）。但是对于其他测试用例，我的解决方案失败了。我没有发现我的解决方案的输出错误。但我不能确定......所以，如果有人解决了它，您能否将您的输出粘贴到以下输入中。

1
4 4
5 5 5 5
9 9 9 9

Answer 1

4096 是我的解决方案在上面的输入中输出的内容

Answer 2

我的解决方案输出：

4096

提示：使用动态规划来解决这个问题。