一看迷宫就是DP或搜索 搜索做法（不可行） 这题的数据范围1e3，用搜索就如开破拖拉机，慢的要死 如果用原始dfs，那么只能过-1的三个测试点，所以我就不展示了 但如果我们适当的剪枝，或许可以过几个测试点 剪枝过程 虽然我们通过剪枝减少了递归次数，但是还是只能过5个测试点 但是，这个记忆性的dfs，不就是dp的原型吗 于是，这题的正解是dp做法 DFS完整代码（不可行） DP做法（可行） 相比于搜索，dp做法就快多了 我们只要定义一个dp数组f 状态：f(x,y)代表走到x,y最多的宝石 我们再定义一个obs数组，表示障碍的位置 bool obs[N][N]; 然后初始化 memset(obs, false, sizeof(obs)); 加两次特判,应对障碍房在出口或入口 然后遍历矩阵 若不为障碍房 转移公式为：f[i][j] = max(f[i-1][j], f[i][j-1]) + a[i][j]; 否则f[i][1] = -1e9; 最后输出就行了 DP完整代码（可行） 点赞吧

题目明确写了只能向下和右方走，明显的 DP。设 dpi,jdp_{i,j}dpi,j 表示走到 (i,j)(i,j)(i,j) 的最大价值。若为障碍，设置为 −∞-\infin−∞，否则得到 dpi,j=max⁡(dpi−1,j,dpi,j−1)+ai,jdp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})+a_{i,j}dpi,j =max(dpi−1,j ,dpi,j−1 )+ai,j 直接转移即可。 建议降橙，它不配黄题。 Code: