LC 70. Climbing Stairs

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
  const q = [[1, 1], [1, 0]]
  const res = pow(q, n)
  return res[0][0]
};

const pow = (a, n) => {
  let ret = [[1, 0], [0, 1]]
  while (n > 0) {
    if ((n & 1) === 1) {
      ret = multiply(ret, a)
    }
    n >>= 1
    a = multiply(a, a)
  }
  return ret
}
const multiply = (a, b) => {
  const c = new Array(2).fill(0).map(() => new Array(2).fill(0))
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
      c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
    }
  }
  return c
}