C++Leecode-70爬楼梯

C++//Leecode-70爬楼梯

题如下：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

实际上是斐波那契

法一：递归+数组存储

class Solution {
public:  
    int climbStairs(int n) {    
        int f[n+1];
        memset(f,0,sizeof(f));
        f[0]=f[1]=1;
        return gett(n,f);
    }
    int gett(int n,int f[])
    {
	   if(f[n]==0) f[n]=gett(n-1,f)+gett(n-2,f);
        return f[n];
    }
};

法二：循环+dp

class Solution {
public:  
    int climbStairs(int n) {    
        if(n==1)return 1;
        if(n==2)return 2;
        int res;
        int op1=1,op2=2;
        for(int i=3;i<=n;i++){
            res=op2;
            op2=op1+op2;
            op1=res;
        }
        res=op2;
        return res;
    }
};

法三：矩阵+快速幂

思想可见此大佬
还有这个

#define ll long long
const ll maxn=1e9+7;
class Solution {
public:  
    ll climbStairs(ll n) {    
        ll a[2][2],res[2][2];
        a[0][0]=0;
        a[0][1]=a[1][0]=a[1][1]=1;
        res[0][0]=res[0][1]=1;
        res[1][0]=res[1][1]=0;
        ksm(n,a,res);
       return res[0][0];
    }
    void mul(ll a[2][2],ll b[2][2]){
        ll op[2][2];
        memset(op,0,sizeof(op));
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    op[i][j]=(op[i][j]+(a[i][k]*b[k][j]));
                }
            }
        }
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                a[i][j]=op[i][j];
            }
        }
        return;
    }
    void ksm(ll n,ll a[2][2],ll res[2][2]){
        for(;n>0;){
            if(n&1) mul(res,a);
            n>>=1;
            mul(a,a);
        }
        return;
    }
};

另：洛谷的1962

	#include
	#define ll long long
	const ll maxn=1e9+7;
	using namespace std;
    void mul(ll a[2][2],ll b[2][2]){
        ll op[2][2];
        memset(op,0,sizeof(op));
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    op[i][j]=(op[i][j]+(a[i][k]*b[k][j])%maxn)%maxn;
                }
            }
        }
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                a[i][j]=op[i][j];
            }
        }
        return;
    }
    void ksm(ll n,ll a[2][2],ll res[2][2]){
        for(;n>0;){
            if(n&1) mul(res,a);
            n>>=1;
            mul(a,a);
        }
        return;
    }
    int main() {    
    	ll n;
    	cin>>n;
        ll a[2][2],res[2][2];
        a[0][0]=0;
        a[0][1]=a[1][0]=a[1][1]=1;
        res[0][0]=0;
        res[0][1]=1;
        res[1][0]=res[1][1]=0;
        ksm(n,a,res);
       cout<
欢迎分享，转载请注明来源：内存溢出
原文地址:https://www.54852.com/zaji/5691317.html