目标
你正在爬一个有 n + 1 级台阶的楼梯，台阶编号从 0 到 n。
你还得到了一个长度为 n 的 下标从 1 开始 的整数数组 costs，其中 costs[i] 是第 i 级台阶的成本。
从第 i 级台阶，你 只能 跳到第 i + 1、i + 2 或 i + 3 级台阶。从第 i 级台阶跳到第 j 级台阶的成本定义为： costs[j] + (j - i)^2
你从第 0 级台阶开始，初始 cost = 0。
返回到达第 n 级台阶所需的 最小 总成本。
示例 1:
输入：n = 4, costs = [1,2,3,4]
输出：13
解释：
一个最优路径是 0 → 1 → 2 → 4
跳跃 成本计算 成本
0 → 1 costs[1] + (1 - 0)^2 = 1 + 1 2
1 → 2 costs[2] + (2 - 1)^2 = 2 + 1 3
2 → 4 costs[4] + (4 - 2)^2 = 4 + 4 8
因此，最小总成本为 2 + 3 + 8 = 13示例 2:
输入：n = 4, costs = [5,1,6,2]
输出：11
解释：
一个最优路径是 0 → 2 → 4
跳跃 成本计算 成本
0 → 2 costs[2] + (2 - 0)^2 = 1 + 4 5
2 → 4 costs[4] + (4 - 2)^2 = 2 + 4 6
因此，最小总成本为 5 + 6 = 11示例 3:
输入：n = 3, costs = [9,8,3]
输出：12
解释：
最优路径是 0 → 3，总成本 = costs[3] + (3 - 0)^2 = 3 + 9 = 12说明:
- 1 <= n == costs.length <= 10^5
- 1 <= costs[i] <= 10^4
思路
有 n + 1 个台阶，初始时在台阶 0，从台阶 i 可以跳跃到 i + 1，i + 2，i + 3，跳跃到台阶 j 的代价为 cost[j - 1] + (j - i)^2，求到达台阶 n 的最小成本。
定义 dp[i] 表示到达台阶 i 的最小成本，状态转移方程为 dp[i] = Math.min(Math.min(dp[i - 2] + costs[i - 1] + 4, dp[i - 1] + costs[i - 1] + 1), dp[i - 3] + costs[i - 1] + 9)。
代码
/**
* @date 2026-11-10 9:04
*/
public class ClimbStairs3693 {
public int climbStairs(int n, int[] costs) {
int[] dp = new int[n + 1];
dp[1] = costs[0] + 1;
if (n >= 2){
dp[2] = Math.min(costs[1] + 4, dp[1] + costs[1] + 1);
}
for (int i = 3; i <= n; i++) {
dp[i] = Math.min(Math.min(dp[i - 2] + costs[i - 1] + 4, dp[i - 1] + costs[i - 1] + 1), dp[i - 3] + costs[i - 1] + 9);
}
return dp[n];
}
}
性能
