LeetCode算法题(Go语言实现)_60

题目

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

一、代码实现（动态规划优化）

func minCostClimbingStairs(cost []int) int {
    n := len(cost)
    if n == 0 {
        return 0
    }
    if n == 1 {
        return cost[0]
    }
    prevPrev, prev := cost[0], cost[1]
    for i := 2; i < n; i++ {
        current := cost[i] + min(prev, prevPrev)
        prevPrev, prev = prev, current
    }
    return min(prev, prevPrev)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

二、算法分析

1. 核心思路

• 滚动数组优化：仅维护前两个状态值
• 状态转移方程：dp[i] = cost[i] + min(dp[i-1], dp[i-2])
• 边界处理：
  • 直接处理n=0和n=1的特殊情况
  • 通过滚动变量避免O(n)空间复杂度

2. 关键步骤

1. 初始化状态：prevPrev=cost[0], prev=cost[1]
2. 迭代计算：
   • 计算当前台阶的最小花费
   • 更新前两个状态值
3. 结果返回：取最后两个状态的最小值

3. 复杂度

三、图解示例

四、边界条件与扩展

1. 特殊场景验证

• 空数组：返回0（题目约束通常不存在）
• 单台阶数组：直接返回cost[0]
• 两台阶数组：取cost[0]和cost[1]较小值
• 大数测试：n=1000时仍能高效计算

2. 扩展应用

• 建筑成本优化：规划多层建筑的最优建造路径
• 游戏AI寻路：动态计算移动消耗最小的路径
• 投资决策：多阶段投资的最小成本路径选择

3. 多语言实现

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n == 1) return cost[0];
        int a = cost[0], b = cost[1];
        for (int i = 2; i < n; i++) {
            int c = cost[i] + Math.min(a, b);
            a = b;
            b = c;
        }
        return Math.min(a, b);
    }
}

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost) == 1:
            return cost[0]
        prev_prev, prev = cost[0], cost[1]
        for i in range(2, len(cost)):
            current = cost[i] + min(prev_prev, prev)
            prev_prev, prev = prev, current
        return min(prev_prev, prev)

五、总结与优化

1. 算法对比

2. 工程优化

• 循环展开：手动展开循环减少分支判断
• SIMD指令：利用并行计算加速向量运算
• 预计算缓存：存储常用值减少重复计算

3. 扩展方向

• 三维路径规划：考虑空间中的多层移动成本
• 随机成本模型：处理概率性变化的动态成本
• 多目标优化：平衡时间和成本的双重约束