领导说我不够积极主动，我说你举个例子？他沉默了三秒。。。

不得不说，算法这东西就像谈恋爱，刚开始觉得挺浪漫，走着走着全是陷阱。这不，前几天写代码时翻出了 LeetCode 的一道“摘樱桃”老题，题号 741，嗯？摘樱桃？我以为是种田模拟，结果一看，实打实的二维动态规划，顺便还来点“走迷宫”的逻辑，属实有点上头。

题目大致意思是这样的：给你一个 N x N 的网格，里面有 0（空地）、1（有樱桃）、-1（障碍），你得从左上角走到右下角，再从右下角走回左上角，两个来回的过程中，尽量多地摘樱桃。

我第一反应是：两趟？这谁设计的，樱桃不能一口气摘完啊？不过想想，也许题目出的人是我老板：凡事都要双检，走一趟怕你偷懒，走两趟更保险（可还行）。

当然啦，不能硬走两次模拟，这复杂度是指数级的，属实爆炸。聪明一点的做法是——两个人同时从 (0,0) 走到 (N-1,N-1)，你想象成他们是两个线程，在一个二维空间上并发摘樱桃，然后选最大值，嘿，有点 MapReduce 内味了。

关键的 DP 状态设计是这样的：

int[][][] dp = newint[N][N][N];

你可能会问，为啥是三维？简单点理解，两个“人”同时走，一共只能走 2N - 2 步，如果当前一个人走了 k 步，那它的位置是 (i, k - i)，另一个人是 (j, k - j)，状态就成了 dp[i][j][k]，表示他们在 k 步内分别走到 (i, k-i) 和 (j, k-j) 所能摘的最多的樱桃数量。

那状态转移呢？我们可以这样写：

for (intk=0; k < 2 * N - 1; k++) {
for (inti=0; i < N; i++) {
for (intj=0; j < N; j++) {
intx1= i, y1 = k - i;
intx2= j, y2 = k - j;
if (y1 < 0 || y1 >= N || y2 < 0 || y2 >= N 
                || grid[x1][y1] == -1 || grid[x2][y2] == -1) {
continue;
            }

intres= grid[x1][y1];
if (x1 != x2 || y1 != y2) {
                res += grid[x2][y2];
            }

intmax= -1;
for (inta= -1; a <= 0; a++) {
for (intb= -1; b <= 0; b++) {
intpi= i + a;
intpj= j + b;
if (pi >= 0 && pj >= 0 && dp[pi][pj][k - 1] >= 0) {
                        max = Math.max(max, dp[pi][pj][k - 1]);
                    }
                }
            }

if (max >= 0) {
                dp[i][j][k] = max + res;
            }
        }
    }
}

当然，这段代码稍微有点臃肿，真实写的时候要注意边界处理。你会发现，这里其实是模拟两条路径同步进行，但只记录一个状态。最后答案就是 dp[N-1][N-1][2*N - 2]，如果没法走通，那就是 0。

有的朋友看到这里会问：这能不能优化空间？三维数组看着太吃内存了。其实可以用滚动数组优化掉一维，不过呢，如果你平时内存富裕，比如 8G 起步，那就别整那些花里胡哨的了，写清楚点不香吗？

说到底，我觉得这题的精髓不只是 DP，而是“路径共享 + 状态压缩”思维。你不能真的两次分别走，那样信息是割裂的，得想办法在一次遍历中模拟双线程协作，这种思路，在分布式或者多线程编程中也很有启发。

有时候我们以为的问题是“摘多少樱桃”，其实核心是“怎么少走弯路”。

别说，这让我想到我平时写代码也是这样：需求文档一遍看不懂，两遍又懒得看，结果自己来来回回走了八遍，最后发现，早把需求吃透，就能少加两次班。

程序员的世界就是这样，很多“樱桃”不是你不配摘，而是你走错了方向。下一次再有人出奇怪算法题，你就别再喊“这题没思路”，而是想想，是不是自己还在走回头路。