LeetCode - 70.Climbing Stair

link: https://leetcode.com/problems/climbing-stairs/description/

题目

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

• 1 <= n <= 45

问题描述

爬楼梯，一次可以爬1层或2层，问到n层有几种方法

问题分析

很显然可以得到通项公式

$$f(n) = f(n - 1) + f(n - 2)$$ 到第1层1种方法，到第2层2种方法，类似fibonacci公式，我们可以设置初始值 $$f(0) = 1$$

$$f(1) = 1$$

方法一：动态规划

这种方法没啥好说的，最多就是常数空间有点用

func climbStairs(n int) int {
    a, b := 1, 1
    for n >= 2 {
        c := a + b
        a = b
        b = c
        n --
    }
    return b
}

方法二：矩阵计算

可以写作矩阵乘法

$$\begin{bmatrix} f(n + 1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} f(n) \\ f(n - 1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}$$

矩阵快速幂

可以参考普通快速幂的方法

type matrix [2][2]int

func pow(m matrix, n int) matrix {
    res := matrix{{1, 0}, {0, 1}}
    for ; n > 0; n >>= 1 {
        if n & 1 == 1{
            res = multiply(res, m)
        }
        m = multiply(m, m)
    }
    return res
}

func multiply(a, b matrix) matrix {
    c := matrix{} 
    for i := 0; i < 2; i ++ {
        for j := 0; j < 2; j++ {
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
        }
    }
    return c
}

func climbStairs(n int) int {
    c := pow(matrix{{1, 1}, {1, 0}}, n)
    return c[0][0]
}

特征值分解

对

$$A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$ 进行特征值分解

A是实对称矩阵，假设存在可逆矩阵P和对角矩阵D使得

$$A = PDP^{-1}$$ 那么就可以得到 $$\begin{bmatrix} f(n + 1) \\ f(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} f(1) \\ f(0) \end{bmatrix} =PD^{n}P^{-1} \begin{bmatrix} f(1) \\ f(0) \end{bmatrix}$$ 得到特征方程 $$det(A-\lambda{I}) = 0 = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix} = \lambda^2-\lambda-1$$ 解出 $$\lambda = \frac{1 \pm \sqrt{5}}{2}$$ 对应${\lambda_1}= \frac{1 + \sqrt{5}}{2}$，求特征向量$v_1$使得$Av_1={\lambda}v_1$

得特征向量

$$v_1= \begin{bmatrix} \frac{1 + \sqrt{5}}{2} \\ 1 \end{bmatrix}$$ 类似的对于${\lambda_2}= \frac{1 - \sqrt{5}}{2}$，求特征向量$v_1$使得$Av_2={\lambda}v_2$

得特征向量

$$v_2 = \begin{bmatrix} \frac{1 - \sqrt{5}}{2} \\ 1 \end{bmatrix}$$ 则构造得到P矩阵和D矩阵 $$P = \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & \frac{1 - \sqrt{5}}{2} \\ 1 & 1 \end{bmatrix}$$

$$D = \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix}$$

则

$$\begin{align} A^n &= PD^nP^{-1} \\ &= \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & \frac{1 - \sqrt{5}}{2} \\ 1 & 1 \end{bmatrix} \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & 0 \\ 0 & \frac{1 - \sqrt{5}}{2} \end{bmatrix}^n \begin{bmatrix} \frac{1 + \sqrt{5}}{2} & \frac{1 - \sqrt{5}}{2} \\ 1 & 1 \end{bmatrix}^{-1} \\ &= \frac{1}{\sqrt{5}} \begin{bmatrix} ({\frac{1 + \sqrt{5}}{2}})^{n + 1} - ({\frac{1 - \sqrt{5}}{2}})^{n + 1} & ({\frac{1 + \sqrt{5}}{2}})^n - ({\frac{1 - \sqrt{5}}{2}})^n \\ ({\frac{1 + \sqrt{5}}{2}})^{n} - ({\frac{1 - \sqrt{5}}{2}})^{n} & ({\frac{1 + \sqrt{5}}{2}})^{n-1} - ({\frac{1 - \sqrt{5}}{2}})^{n-1} \end{bmatrix} \end{align}$$

则

$$f(n) = (({\frac{1 + \sqrt{5}}{2}})^{n + 1} - ({\frac{1 - \sqrt{5}}{2}})^{n + 1}) * \frac{1}{\sqrt{5}}$$ 用代码就是

import "math"

func climbStairs(n int) int {
    sqrt5 := math.Sqrt(5)
    pow1 := math.Pow((1 + sqrt5) / 2, float64(n + 1))
    pow2 := math.Pow((1 - sqrt5) / 2, float64(n + 1))
    return int(math.Round((pow1 - pow2) / sqrt5))
}

方法二：递推数列的通项公式

根据$f(n) = f(n - 1) + f(n - 2)$得到特征方程

$$x^2 = x + 1$$ 假设通解为 $$f(n) = C_{1}x_{1}^n + C_{2}x_{2}^n$$ 这里设置初始值 $$f(1) = 1 \\ f(2) = 1$$ 解得 $$C_1 = \frac{1}{\sqrt{5}}$$

$$C_2 = -\frac{1}{\sqrt{5}}$$

因此通项公式

$$f(n) = (({\frac{1 + \sqrt{5}}{2}})^{n} - ({\frac{1 - \sqrt{5}}{2}})^{n}) * \frac{1}{\sqrt{5}}$$ 这种就和上面的特征值分解类似了

赏

谢谢你请我吃糖果