在公司，不小心摸了一个妹子的手，被投诉，公司要无赔偿让我走人，怎么办？

上周末，刷 LeetCode 刷得脑袋发麻，一道青蛙跳跳跳的题把我搞得半夜三点还在数石头。

题目是这样的：

一只青蛙在数轴上，从位置 0 开始跳跃。每秒钟它要么向左跳一步，要么原地不动，要么向右跳一步。你需要返回它在 T 秒后可能的位置总数。

听起来是不是有点像你上班在工位坐一天，想着左边摸鱼、右边水群、中间装忙，过了 T 个小时到底在哪儿？

说实话，刚看到这题的时候我脑子里第一个冒出来的是递归，觉得没啥难的嘛，青蛙的每一步不就三种选择：左、右、不动。于是写了个 naive 的 DFS：

publicclassFrogPosition {
publicstatic Set<Integer> positions = newHashSet<>();

publicstaticvoiddfs(int pos, int t) {
if (t == 0) {
            positions.add(pos);
return;
        }
        dfs(pos - 1, t - 1);
        dfs(pos, t - 1);
        dfs(pos + 1, t - 1);
    }

publicstaticvoidmain(String[] args) {
intT=3;
        dfs(0, T);
        System.out.println("可能的位置数：" + positions.size());
        System.out.println("所有位置：" + positions);
    }
}

小样，跑个 T = 3，输出 { -3, -2, -1, 0, 1, 2, 3 }，7 个位置，没毛病嘛👍

但再一看题解，发现大家都在讲“动态规划”，我：🫠？

其实再想一想，这题每秒钟青蛙的行为都可以拆解成状态转移。就比如说 T = 2 的时候，青蛙从位置 0 出发：

• • 第 1 秒：能到 -1、0、1
• • 第 2 秒：-1 可以到 -2、-1、0；0 可以到 -1、0、1；1 可以到 0、1、2
• • 最后把所有可能位置合并一下：{-2, -1, 0, 1, 2}

这不就是个标准的 DP 嘛！

所以我后来就写了个 Java 版的动态规划来搞这个事情，空间换时间，效率杠杠的：

publicclassFrogDP {
publicstatic Set<Integer> frogPosition(int T) {
        Set<Integer> current = newHashSet<>();
        current.add(0);

for (inti=0; i < T; i++) {
            Set<Integer> next = newHashSet<>();
for (int pos : current) {
                next.add(pos - 1);
                next.add(pos);
                next.add(pos + 1);
            }
            current = next;
        }

return current;
    }

publicstaticvoidmain(String[] args) {
intT=4;
        Set<Integer> result = frogPosition(T);
        System.out.println("T 秒后青蛙可能在的位置：" + result);
        System.out.println("一共能到达的点数：" + result.size());
    }
}

每次都把上一秒的所有位置拿出来，拓展到下一秒的所有可能。暴力但不愚蠢，毕竟最多就是三的 T 次方种情况，T 太大也别干了，直接跑路🐸。

有同事看我写这个问：“为啥不用数组记录每秒的状态？”兄弟，不用你提醒，我也在想优化内存好嘛😤

不过说真的，其实这题就是典型的“状态爆炸但边界有限”，如果你能意识到每一步的状态只跟前一步相关，就可以一步步把空间压缩下来，甚至用一个 HashSet 复用就行。

而且这类题其实在刷算法时经常遇到，特别适合练思维建模。我觉得最大的收获不是“青蛙在哪儿”，而是它让我重新审视了状态转移这件事。

写代码这么多年（咳咳，不是剧透），我逐渐发现很多“动态规划”的难点不是代码本身，而是你能不能看出“状态”和“转移”两个维度。有时候你一上来就想着暴力搜索，那真的会写得头皮发麻，然后才慢慢悟出，哦，原来可以状态复用呀。

就像青蛙跳跃，一步三选，但真正的重点在于你有没有静下心来分析它的“可能性”结构，而不是盯着跳的动作。

不过有一说一，这题最适合的解法其实还真不一定是 DP，因为状态数不多，暴力都能跑得很快。所以如果是面试遇到，我建议上来先提思路，让面试官知道你有 DP 思维，然后再来个暴力优化版，说不定更有戏😉

毕竟程序员不就像这只青蛙吗？每秒钟都面临左边的需求、右边的 Bug、中间的 review，我们终其一生都在数轴上跳来跳去，跳着跳着就秃了……

你们说呢？T 秒后，你可能还在原地……但也可能已经是架构师了😎