忍者在练习飞檐走壁。现在有两排房子。从左往右排列各有 n 间。如下图。在每个房间的房顶。他有 6 个选择:
第一排:1 2 3 ... n
本题是一个典型的动态规划问题。忍者的目标是从第一排或第二排的房间 1 出发,到达第一排或第二排的房间 n,要求最小化消耗的时间。根据题意,我们可以从每个房间选择不同的路径(在两个房间之间跳跃或在同一排内移动),每种路径都有不同的消耗时间。我们需要通过动态规划来计算从起点到终点的最短时间。
我们可以定义动态规划的状态如下:
dp1[i]
表示从第一排的房间 i 出发,到达第 i 个房间所需的最小时间。dp2[i]
表示从第二排的房间 i 出发,到达第 i 个房间所需的最小时间。