有人能找到一种方法来解决这个复杂度为 O(logn) 的问题吗？

Question

我正在做leetcode日常问题（01/17/24），爬楼梯，我已经完成了这个问题，但是复杂度为O(n)。我想知道是否有人可以想出一个更快、更有效的解决方案来分享。

这是我在 O(n) 复杂度下得到的结果：

public class Solution {
    public int ClimbStairs(int n) {
        //quick base case
        if (n <= 3 && n > 0) return n;

        //working total variables
        int total = 6, now = 2, next = 3;

        //for loop to calculate total
        for (int index = 3; index < n; index++) {
            total = now + next;
            now = next;
            next = total;
        }
        return total;
    }
}

Answer 1

让我们尝试找出递推关系。如果我们想知道 𝑛 的可能性数量（我们称之为 𝑇_𝑛），那么我们可以考虑两种情况：

1. 我们先走一小步（1），然后可能性的数量是𝑇_𝑛−1
2. 我们先迈出一大步（2），然后可能性的数量是𝑇_𝑛−2

这些的总和就是解决方案：

𝑇_𝑛 = 𝑇_𝑛−1 + 𝑇_𝑛−2

这是斐波那契递推关系。

所以代码可能是这样的：

class Solution {
    // Keep track of Fibonacci numbers across different runs:
    static ArrayList<Integer> fib = new ArrayList<>(Arrays.asList(1, 1));

    public int climbStairs(int n) {
        // If we don't have this Fibonacci number yet, extend what we have:
        for (int i = fib.size(); i <= n; i++) { 
            fib.add(fib.get(i - 2) + fib.get(i - 1));
        }
        // And now just return it:
        return fib.get(n);
    }
}

当然，现在您可以查看挑战的约束，并注意𝑛最多为 45。因此您甚至可以预先计算前 46 个斐波那契数并将它们存储在原始数组中。