一天一大 leet(爬楼梯)难度:简单 DAY-13
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：
给定 n 是一个正整数。
示例：
- 示例 1
输入：2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶- 示例 2
输入：3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶抛砖引玉
- 传入不同n之间输出规律;
- 当n>2时每增加一个数，就会出现最后一次到达这个数的来源就会有两个;
// 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)- 总结逻辑就是f(n)=f(n-2)+f(n-1);
- 那么就可以只知道最开始的两个结果就可以推断后面所有的结果了;
/**
* @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 次方的形式，那么可以用快速幂来加速计算
- 如果一个递归式形如
即齐次线性递推式， 我们就可以把数列的递推关系转化为矩阵的递推关系，即构造出一个矩阵的 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;
};菜鸡的自白
港真矩阵快速幂和通项公式确实没看懂，数学不行真是不行呀
路漫漫其修远兮
举报
腾讯云开发者
