LeetCode - 70.Climbing Stair

2024-08-18

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}} \] 这种就和上面的特征值分解类似了