解题思路
机器人只能向右或向下走,到达每个格子的路径互不回头,可以用网格动态规划求最小调节能耗。
- 设 dp[i][j] 表示从 (0,0) 走到 (i,j) 的最小总调节能耗。起点没有移动,所以 dp[0][0]=0。
- 走到 (i,j) 只可能来自上方 (i−1,j) 或左方 (i,j−1)。从上一格走过来这一步的消耗是两格灰尘浓度差的绝对值。
- 因此 dp[i][j] 取两种来源的较小值:来自上方时加上 ∣di,j−di−1,j∣,来自左方时加上 ∣di,j−di,j−1∣。第一行没有上方,第一列没有左方,只保留存在的那一侧。
- 答案是 dp[r−1][c−1]。