LC 70. Climbing Stairs

/**
 * @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
}



如希望撰写评论,请发邮件至 me@tianhegao.com (直接点击邮箱可自动跳转至默认邮箱App,并填写收信人和邮件主题)或者点击这里在线留言,我会挑选对读者有价值的评论附加到文章末尾。



可通过以下渠道赞赏此文