朝阳建设网站,成都网站建设前十,2022新闻热点事件简短30条,北京市网站制作原题链接#xff1a;爬楼梯 个人解法
思路#xff1a;
动态规划 状态表示#xff1a;f[i]表示走到第n阶台阶有几种方法 状态转移#xff1a;f[i] f[i -1] f[i - 2]
这实际上就是斐波那契数列#xff0c;通过转移可以看到#xff0c;我们只用了三个变量#xff0c;故… 原题链接爬楼梯 个人解法
思路
动态规划 状态表示f[i]表示走到第n阶台阶有几种方法 状态转移f[i] f[i -1] f[i - 2]
这实际上就是斐波那契数列通过转移可以看到我们只用了三个变量故可以不用状态数组而只用三个变量进行转移。
时间复杂度O(n)O(n)O(n)
代码
class Solution {
public:int climbStairs(int n) {int a 1, b 1, c 1;for(int i 2;i n;i ) {c a b;a b, b c;}return c;}
};更好的解法
斐波那契数列矩阵表示 由递推可以得到
故我们可以利用矩阵乘法快速幂求出MnM^nMn从而求除FnF_nFn
利用解析解
斐波那契数列解析解
由矩阵表示可以看到MMM矩阵为可逆矩阵且MMM可相似对角化从而表示为MSΛS−1其中Λ为由特征值S为特征向量组成的矩阵M S\Lambda S^{-1}其中\Lambda为由特征值S为特征向量组成的矩阵MSΛS−1其中Λ为由特征值S为特征向量组成的矩阵
那么MnSΛnS−1从而求出Fn的解析解那么M^n S\Lambda^{n}S^{-1}从而求出F_n的解析解那么MnSΛnS−1从而求出Fn的解析解
