我正在尝试学习动态编程技术.我正在阅读本教程 - 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.