一天一大 leet(爬楼梯)难度:简单 DAY-13

20200613

题目(难度:简单):

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意

给定 n 是一个正整数。

示例

1. 示例 1

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  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);
};

官方答案

1. 动态规划

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

2. 矩阵快速幂

构建这样一个递推关系：

$\begin{vmatrix} \mathbf{1} & \mathbf{1} \\ \mathbf{1} & \mathbf{0} \\ \end{vmatrix} \begin{vmatrix} \mathbf{f(n)} \\ \mathbf{f(n-1)} \\ \end{vmatrix}= \begin{vmatrix} \mathbf{f(n)+f(n-1)} \\ \mathbf{f(n)} \\ \end{vmatrix}= \begin{vmatrix} \mathbf{f(n+1)} \\ \mathbf{f(n)} \\ \end{vmatrix}$∣∣∣∣​11​10​∣∣∣∣​∣∣∣∣​f(n)f(n−1)​∣∣∣∣​=∣∣∣∣​f(n)+f(n−1)f(n)​∣∣∣∣​=∣∣∣∣​f(n+1)f(n)​∣∣∣∣​

因此：

$\begin{vmatrix} \mathbf{f(n+1)} \\ \mathbf{f(n)} \\ \end{vmatrix}= \begin{vmatrix} \mathbf{1} & \mathbf{1} \\ \mathbf{1} & \mathbf{0} \\ \end{vmatrix}^n \begin{vmatrix} \mathbf{f(1)} \\ \mathbf{f(0)} \\ \end{vmatrix}$∣∣∣∣​f(n+1)f(n)​∣∣∣∣​=∣∣∣∣​11​10​∣∣∣∣​n∣∣∣∣​f(1)f(0)​∣∣∣∣​

令：

$M= \begin{vmatrix} \mathbf{1} & \mathbf{1} \\ \mathbf{1} & \mathbf{0} \\ \end{vmatrix}$M=∣∣∣∣​11​10​∣∣∣∣​

因此我们只要能快速计算矩阵 M 的 n 次幂，就可以得到 f(n) 的值。如果直接求取 $M^n$Mn

时间复杂度是 O(n) 的，我们可以定义矩阵乘法，然后用快速幂算法来加速这里 $M^n$Mn的求取

如何想到使用矩阵快速幂？

• 如果一个问题可与转化为求解一个矩阵的 n 次方的形式，那么可以用快速幂来加速计算
• 如果一个递归式形如 $f(n) = \sum_{i = 1}^{m}a_i f(n - i)$f(n)=∑i=1m​ai​f(n−i) 即齐次线性递推式，
  我们就可以把数列的递推关系转化为矩阵的递推关系，即构造出一个矩阵的 n 次方乘以一个列向量得到一个列向量， 这个列向量中包含我们要求的 f(n)。一般情况下，形如 $f(n) = \sum_{i = 1}^{m} a_i f(n - i)$f(n)=∑i=1m​ai​f(n−i) 可以构造出这样的 mxm 的矩阵：
  $\begin{vmatrix} \mathbf{a_1} & \mathbf{a_2} & \mathbf{a_3} & \mathbf{...} & \mathbf{a_m} \\ \mathbf{1} & \mathbf{0} & \mathbf{0} & \mathbf{...} & \mathbf{0} \\ \mathbf{0} & \mathbf{1} & \mathbf{0} & \mathbf{...} & \mathbf{0} \\ \mathbf{0} & \mathbf{0} & \mathbf{1} & \mathbf{...} & \mathbf{0} \\ \mathbf{...} & \mathbf{...} & \mathbf{...} & \mathbf{...} & \mathbf{...} \\ \mathbf{0} & \mathbf{0} & \mathbf{1} & \mathbf{...} & \mathbf{1} \\ \end{vmatrix}$∣∣∣∣∣∣∣∣∣∣∣∣​a1​100...0​a2​010...0​a3​001...1​..................​am​000...1​∣∣∣∣∣∣∣∣∣∣∣∣​
• 那么遇到非齐次线性递推我们是不是就束手无策了呢？其实未必。有些时候我们可以把非齐次线性递推转化为其次线性递推，比如这样一个递推：
  $f(x)=(2x−6)c+f(x−1)+f(x−2)+f(x−3)$f(x)=(2x−6)c+f(x−1)+f(x−2)+f(x−3)

我们可以做这样的变换：
$f(x)+xc=[f(x−1)+(x−1)c]+[f(x−2)+(x−2)c]+[f(x−3)+(x−3)c]$f(x)+xc=[f(x−1)+(x−1)c]+[f(x−2)+(x−2)c]+[f(x−3)+(x−3)c]

令 $g(x) = f(x) + xc$g(x)=f(x)+xc，那么我们又得到了一个齐次线性递：

$g(x) = g(x - 1) + g(x - 2) + g(x - 3)$g(x)=g(x−1)+g(x−2)+g(x−3)

/**
 * @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(n) = f(n - 1) + f(n - 2)$f(n)=f(n−1)+f(n−2)，我们可以写出这样的特征方程：
$x^2 = x + 1$x2=x+1
求得：$x_1 = \frac{1+\sqrt{5}}{2}，x_2 = \frac{1-\sqrt{5}}{2}$x1​=21+5​​，x2​=21−5​​，设通解为 ：$f(n) = c_1^n + c_2^n$f(n)=c1n​+c2n​ ，代入初始条件 f(1) = 1f，f(2) = 1，得：$c_1 = \frac{1}{\sqrt{5}}，c_2 = -\frac{1}{\sqrt{5}}$c1​=5​1​，c2​=−5​1​，我们得到了这个递推数列的通项公式：

$f(n) = \frac 1{\sqrt{5}}[(\frac {1-\sqrt{5}}y)^n-(\frac {1+\sqrt{5}}y)^n]$f(n)=5​1​[(y1−5​​)n−(y1+5​​)n]

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

菜鸡的自白

港真矩阵快速幂和通项公式确实没看懂，数学不行真是不行呀

路漫漫其修远兮

博客: 小书童博客(http://gaowenju.com/)

公号: 坑人的小书童