从 LeetCode 1219 与 3459 看动态规划何时成立
LeetCode 1219《黄金矿工》与 3459《最大 V 型对角线》，正好构成了一组极具代表性的对比样本。
本文尝试通过对这两道题的对照分析，讨论一个核心问题：
一个问题'能不能 DP'，本质上取决于什么？
首先我们大概看一下题
1. LeetCode 1219：黄金矿工
- 给定一个网格，每个格子有一定数量的黄金（或为 0）
- 可以从任意非 0 格子出发
- 路径上所有格子都必须非零
- 每个格子最多访问一次
- 上下左右移动
- 目标：收集尽可能多的黄金
这是一个典型的'网格路径最大化'问题。
2. LeetCode 3459：最大 V 型对角线
- 给定一个矩阵
- 寻找形如 V 字的对角线路径
- 路径方向固定
- 在某个拐点处由一条对角线切换到另一条对角线
- 目标：最大化路径权值
同样是路径问题，但官方/主流解法是动态规划。
为什么 1219 不该用 DP？
1. 必须面对的状态定义
如果我们尝试为 1219 定义 DP 状态，会很快遇到一个现实问题：
使用 dp[x][y] 来代表从当前位置开始期望得到的最大黄金数量？
这个定义是不成立的。
原因在于：
从同一个 (x, y) 出发，未来能走哪些格子，完全取决于'之前已经走过哪些格子'
因此，完整状态至少应为：
(x, y, visited)
其中 visited 是一个集合（或位掩码），表示已经访问过的格子。
2. visited 带来的根本问题
一旦状态中包含 visited：
- 状态数量呈指数级增长
- 不同路径顺序会生成完全不同的状态
- 不存在一个统一的计算顺序
更重要的是：
无法找到一个顺序，使得所有状态只依赖于'已经计算过'的状态
也就是说：
- 状态依赖图虽然是 DAG
- 但无法线性化
这正是 DP 填表'无从下手'的根本原因。
3. 本质判断
1219 的问题本质是：
在网格图中，寻找一条 权值最大的简单路径
而'简单路径 + 任意拐弯 + 不可重复访问'，天然就是搜索问题，而不是状态累积问题。
因此，DFS + 回溯并不是'退而求其次'，而是最符合问题结构的解法。
为什么 3459 可以自然地 DP？
与 1219 形成鲜明对比，3459 具备 DP 的一系列'理想条件'。
1. 路径方向固定
V 型路径可以拆分为两段：
- 一段沿固定对角线方向前进
- 另一段沿另一固定对角线方向前进
例如：
(i, j) 只依赖于 (i-1, j-1) 以及当前方向
这立即带来了一个关键性质：
存在天然的先后顺序（拓扑序）
2. 子问题含义稳定
在 3459 中，一个常见状态是：
dp[i][j][dir]
其含义是：
