题干分析 题设给定一个花费数组,已知我们可以上1/2/3级台阶,每次上到台阶i要花费costs[i],同时根据上的台阶级数,追加花费1/4/9的花费。求从台阶0开始上到台阶n的最小花费为多少。 算法思路 拆分问题: 到达台阶n我们只能从台阶n-1/n-2/n-3开始分别花费对于的启动花费并追加移动花费到达台阶n。由此,我们设计dp[i]记录到达第i节台阶的最小花费,不难得到状态转移方程: 同时有初始条件: 同时我们注意到整个DP过程只涉及连续的四个状态值,因此可以进一步优化为常数额外空间消耗的迭代形式。 实现代码 递归与未进行内存优化的写法已注释 class Solution { /*...