假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:
给定 n 是一个正整数。
示例:
输入:2
输出:2
解释:有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
输入:3
输出:3
解释:有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
// 3
1->3 2->3 => f(3)=f(1)+f(2)
// 4
2->4 3->4 => f(4)=f(2)+f(3)
// 5
3->5 4->5 => f(5)=f(3)+f(4)
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
if (n < 2) return 1;
if (n === 2) return 2;
let map = new Map([[0, 1], [1, 1]]);
for (let i = 2; i < n + 1; i++) {
map.set(i, map.get(i - 2) + map.get(i - 1));
}
return map.get(n);
};
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let p = 0, q = 0, r = 1;
for (let i = 1; i <= n; ++i) {
p = q;
q = r;
r = p + q;
}
return r;
}
构建这样一个递推关系:
因此:
令:
因此我们只要能快速计算矩阵 M 的 n 次幂,就可以得到 f(n) 的值。如果直接求取
时间复杂度是 O(n) 的,我们可以定义矩阵乘法,然后用快速幂算法来加速这里
的求取
如何想到使用矩阵快速幂?
即齐次线性递推式, 我们就可以把数列的递推关系转化为矩阵的递推关系,即构造出一个矩阵的 n 次方乘以一个列向量得到一个列向量, 这个列向量中包含我们要求的 f(n)。一般情况下,形如
可以构造出这样的 mxm 的矩阵:
我们可以做这样的变换:
令
,那么我们又得到了一个齐次线性递:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
var q = [[1, 1], [1, 0]];
var res = pow(q, n);
function pow(a, n) {
var ret = [[1, 0], [0, 1]];
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
function multiply(a, b) {
var c = [Array(2), Array(2)];
for (var i = 0; i < 2; i++) {
for (var j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}
return res[0][0];
};
3. 通项公式
根据递推方程
,我们可以写出这样的特征方程:
求得:
,设通解为 :
,代入初始条件 f(1) = 1f,f(2) = 1,得:
,我们得到了这个递推数列的通项公式:
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
var sqrt5 = Math.sqrt(5);
var fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return parseInt(fibn / sqrt5);
};
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
var a = 1;
var b = 1;
while(n--){
a = (b+=a) -a;
}
return a;
};
港真矩阵快速幂和通项公式确实没看懂,数学不行真是不行呀
路漫漫其修远兮