思路与证明

• 状态定义：设 $dp[i][j]$ 为到达格子 $(i, j)$ 的最小能耗。

• 状态转移：由于只能向右或向下移动，有

  • $dp[i][j]$ = $\text{grid}[i][j]$ + $\min(dp[i-1][j],dp[i][j-1])$

• 边界条件：

  • 第一行：$dp[0][j] = dp[0][j-1] + \text{grid}[0][j]$
  • 第一列：$dp[i][0] = dp[i-1][0] + \text{grid}[i][0]$

题目内容

在实际的无人机物流配送场景中，无人机需要从仓库(左上角网格点)出发，将货物送达目的地(右下角网格点)。为了优化飞行效率，我们将其飞行区域划分为 $m$ 行 $n$ 列的网格状单元格，每个单元格的数值表示该区域的单位能耗成本(非负整数，包含地形、风阻等因素影响)。由于无人机受限于飞行规则(如避免频繁转向、遵守临时禁飞区管制)，每次只能向右或向下移动一个单元格。请为无人机规划一条从起点到终点的飞行路径，使得全程的总能耗成本最小。