无法弄清楚为什么DP方法不起作用

Question

我正在尝试学习动态编程技术.我正在阅读本教程 - https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/.

请阅读的问题,问题陈述StarAdventure的Advanced部分.

我不明白为什么我们不能只使用经典的DP方法找到从左上角到右下角三次的最佳路径,每次都找到最佳路径中找到的苹果.有人可以解释使用示例案例为什么这种方法不起作用.

问题描述:

给定具有M行和N列(N×M)的矩阵.在每个细胞中都有许多苹果.你从矩阵的左上角开始.你可以向下或向右一个单元格.你需要到达右下角.然后你需要通过向左或向上移动一个单元格的每个步骤返回到左上角的单元格.到达这个左上角的单元格后,你需要再次回到右下角的单元格.找到您可以收集的最大苹果数量.当你通过一个牢房 - 你收集那里留下的所有苹果.

限制:

1 < N,M <= 50; 每个单元格包含0到1000个苹果,包括0和1000.

Answer 1

您的算法可能会做出错误的决定,因为从一开始就没有考虑到您将有其他机会获得大奖励,从而降低您的总数.

例:

S 0 0 50 1
1 1 1 0 1
1 1 1 0 1
1 1 1 50 1
1 1 1 50 E

你的算法将是S-0-0-50-0-0-50-50-E,然后是E-50(0)-1-1-1-1-1-1-S,然后是S-0-1 -1-1-1-50(0)-1-E.总共得到0个苹果7次(总奖励3*50 + 7*0 + 11*1 = 161).

你可以做得更好:S-0-0-50-1-1-1-1-E,然后是E-50-1-1-1-1-1-1-S,然后是S-0-1 -1-1-1-50-1(0)-E,总共给你3*150 + 4*0 + 14*1 = 164个苹果.

所以你可以使用DP,但不能只用一次从S到E,然后再一次用ES,然后再用SE.你必须立刻思考完整的道路.