解题思路

机器人只能向右或向下走，到达每个格子的路径互不回头，可以用网格动态规划求最小调节能耗。

设 $dp[i][j]$ 表示从 $(0,0)$ 走到 $(i,j)$ 的最小总调节能耗。起点没有移动，所以 $dp[0][0]=0$ 。
走到 $(i,j)$ 只可能来自上方 $(i-1,j)$ 或左方 $(i,j-1)$ 。从上一格走过来这一步的消耗是两格灰尘浓度差的绝对值。
因此 $dp[i][j]$ 取两种来源的较小值：来自上方时加上 $|d_{i,j}-d_{i-1,j}|$ ，来自左方时加上 $|d_{i,j}-d_{i,j-1}|$ 。第一行没有上方，第一列没有左方，只保留存在的那一侧。
答案是 $dp[r-1][c-1]$ 。

题目内容

请规划一条清洁路线，使机器人从房间左上角走到右下角时，功率控制系统消耗的总调节能量最小。

房间是 $r$ 行 $c$ 列的网格。第 $i$ 行第 $j$ 列格子的灰尘浓度为非负整数 $d_{i,j}$ 。机器人从 $(0,0)$ 出发，只能向右或向下走一格，终点是 $(r-1,c-1)$ 。途中会经过格子上的灰尘。

相邻两格 $A$ 、 $B$ 的灰尘浓度分别为 $d_A$ 、 $d_B$ 时，控制系统要把功率从 $d_A$ 调到 $d_B$ ，这一步消耗的调节能量为 $|d_B-d_A|$ 。例如从灰尘 $4$ 走到灰尘 $7$ ，消耗 $|7-4|=3$ 。整条路径上每一步消耗之和就是总调节能耗。

第一行两个整数 $r$ 、 $c$ （ $1 \le r, c \le 200$ ），表示网格的行数和列数。

接下来 $r$ 行，每行 $c$ 个整数 $d_{i,j}$ （ $0 \le d_{i,j} \le 10000$ ），表示各格子的灰尘浓度。

输出一个整数，表示最小总调节能耗。

输入

1 4
2 2 5 1

输出

说明

只有一条路 $2 \to 2 \to 5 \to 1$ ，调节能耗为 $|2-2|+|5-2|+|1-5|=0+3+4=7$ 。

输入

输出

说明

走 $0 \to 1 \to 2 \to 3$ ，调节能耗为 $|1-0|+|2-1|+|3-2|=1+1+1=3$ 。这是最小总调节能耗。

选择提交后点击「开始AI分析」