吃最多数量苹果问题：双路动态规划（DP）参考解法

shaowu459

题意说明：
1）在10*10的苹果园中，每个格子数值代表苹果的数量。
2）diss从左上角（B2）出发一路吃到右下角（K11），然后一路吃回出发点（B2）。
3）去程每次只能向右或向下走，返程每次只能向左或向上走。
4）第一次经过任意格子，该格子中的所有苹果都会被diss吃掉，并且不再生。

问：diss最多能吃多少苹果（返回一个正整数）。

shaowu459

可能得路线举例如下（请忽略数字），第一个图去程走棕色路线，返程走黄色路线，两条路线除了首尾外不交叉。
第二个图去程走棕色路线，返程走黄色路线，但可能交叉，交叉处的苹果只能吃一次。

shaowu459

由于规划求解有“无后效性”的要求，所以按之前的从左上角到右下角取最大值，然后再应用一遍从右下角到左上角取最大值的方法，对本题来说不可行。

shaowu459

可以视同A、B两个人同时从起点出发，到右下角走。有交叉也没有关系，可以视同交叉后A始终走行数较大的路径。

shaowu459

在上述思路下，假设A、B从起点各走了k步，所处行号分别为x1和x2，则相关数据主要有以下特点：

shaowu459

可以设置状态dp[k][x1][x2]，代表：A、B各走k步，A在x1行，B在x2行时可吃的最多苹果数量。

shaowu459

接上楼四种状态举例：

shaowu459

具体分析相关数据的取值范围：

shaowu459

为方便处理，可以把各种状态标识，也就是k、x1和x2连接成字符串。

shaowu459

状态值更新举例：