题干分析 题设给定一个爬楼花费数组,记录每到一个台阶需要再向上爬所需的花费。要求我们求解从下标0或者1开始爬楼到达楼顶所需最小花费。 算法思路 基本的线性DP问题。根据题设我们可以假设初始我们从下标-1处出发,到下标0或者下标1,此次出发无花费。因此设数组表示到达下标为i的台阶所需花费,初始条件为: 我们的目标是到达楼顶,即求。 我们将总目标进行拆分:由于到达下下标为n的台阶只可能是从下标n-1的台阶上花费cost[n-1]上来,或者从下标n-2上花费cost[n-2]上来,我们取其中的最小值,由此DP状态转移方程为: 同时我们不难观测到整个DP状态转移过程只涉及相邻的三个DP状态,完全可...