/**
* @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,并填写收信人和邮件主题)或者点击这里在线留言,我会挑选对读者有价值的评论附加到文章末尾。
可通过以下渠道赞赏此文
- 爱发电
- Paypal(定额 5 美元)