本题是一个典型的动态规划问题。目标是从第 1 列的某一轨道出发,最终抵达第 n 列的任意轨道,要求最小化总代价。根据题意,我们可以从每个节点选择不同的移动方式(在同轨道前进或跨轨道移动),每种方式都有不同的代价。我们需要通过动态规划来计算从起点到终点的最小代价。
我们可以定义动态规划的状态如下:
dp1[i] 表示到达节点 A_i 的最小代价。dp2[i] 表示到达节点 B_i 的最小代价。在一个由两条平行轨道组成的通道中,每条轨道上等距排列着 n 个节点,分别给出两条轨道上节点的能量值序列 A 和 B。
你将从第 1 列的某一轨道出发,希望最终抵达第 n 列的任意轨道。移动过程中只能前进,允许的移动方式共有六种:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册