1.问题描述
小D接到一项任务，要求他爬到一座n层大厦的顶端与神秘人物会面。这座大厦有一个神奇的特点，每层的高度都不一样，同时，小D也拥有一项特殊能力，可以一次向上跳跃一层或两层，但是这项能力无法连续使用。已知向上1高度消耗的时间为1，跳跃不消耗时间。由于事态紧急，小D想知道他最少需要多少时间到达顶层。
输入格式：
第一行包含一个整数n，代表楼的高度。
接下来n行每行一个整数ai，代表i层的楼层高度（ai <= 100）。
输出格式：
输出1行，包含一个整数，表示所需的最短时间。
2.题目分析
这道题很像Leedcode里面的一道经典例题青蛙跳台阶 只不过这道题里有两种状态 跳和爬
按照动态规划的一般思路:1定义数组含义 2找到递推关系 3赋予初值
3.算法设计
先看，到达第i层（如果i很大很大，这么说是为了防止特殊情况），那么到第i层有2种做法：
跳和爬。问题要求我们求最短时间，那我们不妨就设一个关于最短时间的数组，容易想到，因为最短时间不仅涉及到楼层数，还涉及到到达第i层的做法，我们不妨设一个二维数组dp[i][j]表示到达第i层的最小费用。那么现在讨论 做法和j的关系：到达第i层楼，我们实际上有三种做法 ：1>>从i-1层爬上去 ，2>>从i-1层跳上去， 3>>从i-2层跳上去
因而我们应该这样定义：
""dp[i][0]代表爬到第i层 花费时间
dp[i][1]代表到跳第i层 花费时间 从i-1上来
dp[i][2]代表到跳第i层 花费时间 从i-2上来""
定义完数组含义，下面就是要寻找递推关系：
考虑dp[i][0]，根据其含义，我们可知，dp[i][0]=a[i]+min(dp[i-1][0],dp[i-1][1],dp[i-1][2])
具体来说，就是既然已知是爬到i层，而到i层有三种做法：从i-1爬上来，从i-1跳上来，从i-2跳上来。因而取这三种做法的最小值 可达到目的
考虑dp[i][1]，根据其含义，我们可知，dp[i][1]=dp[i-1][0]
具体来说，就是既然已知是从i-1层跳到第i层，且题意说明不可连续跳，那么在从i-1层出发，只能是爬到i层，因而费用等于爬到i-1层的费用
同理可得 dp[i][2]=dp[i-2][0]
定义好数组并找到了递推关系，现在只需要赋予初值：由递归关系下标可知,i>=2，那么我们对dp[0],dp[1]，进行赋值。dp[0]=[0,0,0]，dp[1]=[a[1],0,0]
（这里读者模拟一下dp[2]的形成过程就可知晓）
4.代码实现
n=int(input()) a=[] for i in range(n): a.append(int(input())) a.insert(0,0) dp=[[0,0,0] for i in range(n+1)] dp[1]=[a[1],0,0] for i in range(2,n+1): for j in range(3): if j==0: dp[i][0]=a[i]+min(dp[i-1][0],dp[i-1][1],dp[i-1][2]) elif j==1: dp[i][1]=dp[i-1][0] else: dp[i][2]=dp[i-2][0] print(min(dp[n]))
看完如果有收获~麻烦点个三连可以吗！！
后续有任何不懂的都可以来私信我~
我是小郑 正在备战蓝桥杯 奔赴热爱 奔赴山海！
