I saw most solutions posted in discussion are DP with runtime O(n) and O(1) space which is accepted by OJ.

The only O(log(n)) solution so far is **lucastan's** using Binet's formula.

There actually is a matrix multiplication solution which also runs in O(log(n)). It basically calculates fibonacci numbers by power of matrix ((0, 1), (1, 1)) ^ (n-1).

```
public int climbStairs1(int n) {
int[][] a = {{0, 1}, {1, 1}};
int[][] m = pow(a, n - 1);
return m[0][1] + m[1][1];
}
private int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
private int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
```