爬楼梯最小成本两种Java解法的时间复杂度差异求助

我针对最小花费爬楼梯问题实现了两种Java解法，提交后性能差距明显：

• 第一种耗时1ms，超过89.65%的Java提交
• 第二种耗时2ms，仅超过39.33%的Java提交

两者逻辑看似相近，但耗时差了一倍，下面先贴出两种解法的代码，再分析背后的细节差异。

解法1（1ms） #

public int minCostClimbingStairs(int[] cost) {
    // 数组长度比cost长1，把"楼顶"当作最后一个要到达的台阶
    int minimumCost[] = new int[cost.length + 1];
    
    // 从第2级开始遍历，因为到达第0、1级的最小花费都是0
    for (int i = 2; i < minimumCost.length; i++) {
        int takeOneStep = minimumCost[i - 1] + cost[i - 1];
        int takeTwoSteps = minimumCost[i - 2] + cost[i - 2];
        minimumCost[i] = Math.min(takeOneStep, takeTwoSteps);
    }
    
    // 数组最后一个元素就是到达楼顶的最小花费
    return minimumCost[minimumCost.length - 1];
}

解法2（2ms） #

public int minCostClimbingStairs(int[] cost) {
    //cost: 0 ->n-1
    //dp: 1->n
    int[] dp = new int[cost.length+1];
    dp[0]=0;
    dp[1]=0;
    //k=2
    for(int i=1;i<cost.length;i++) {
        dp[i+1] = cost[i] + Math.min(dp[i], dp[i-1]);
    }
    
    return Math.min(dp[cost.length], dp[cost.length-1]);
}

差异细节分析 #

首先明确：两种解法的时间复杂度都是O(n)，耗时差异并非来自复杂度等级，而是实现细节带来的常数项开销差异，具体如下：

1. 递推逻辑与最终计算的冗余 #

• 解法1的数组minimumCost[i]直接定义为「到达第i级台阶（包括楼顶）的最小花费」，递推时直接把楼顶纳入计算范围，最后只需返回数组最后一个元素，无需额外计算。
• 解法2的dp数组定义不够贴合问题终点，循环结束后还需要额外调用一次Math.min(dp[cost.length], dp[cost.length-1])来确定到达楼顶的最小花费，多了一次O(1)的操作。虽然单次操作开销极小，但在大量测试用例的累积下，会体现出耗时差异。

2. JIT编译优化的差异 #

两种解法的递推表达式结构不同：

• 解法1先计算两种路径的总花费（takeOneStep和takeTwoSteps），再取最小值赋值；
• 解法2先取前两级的花费最小值，再加上当前台阶的花费。

这种结构差异会影响Java即时编译器（JIT）的优化程度：解法1的逻辑更直白，JIT更容易将数组访问优化为寄存器操作，减少内存访问的开销；而解法2的嵌套计算结构，可能让JIT的优化难度更高，导致实际运行时的指令开销更大。

3. 数组初始化的冗余操作 #

解法2中手动设置了dp[0]=0和dp[1]=0，但Java中int数组的默认初始值就是0，这两步属于冗余操作。虽然这部分开销几乎可以忽略，但也是细微的性能损耗点。

4. 缓存局部性的细微差异 #

解法1在循环中访问的cost元素是i-1和i-2，属于连续的前序元素，更符合CPU缓存的局部性原理；而解法2访问的是cost[i]，是当前循环对应的元素，缓存命中率略低于解法1，这也会带来微小的性能差异。

内容的提问来源于stack exchange，提问作者coder0h1t