首页 > 其他分享 >70. 爬楼梯(/dp)

70. 爬楼梯(/dp)

时间:2023-02-26 00:44:23浏览次数:62  
标签:爬楼梯 int ret vector sqrt5 70 return public dp

原题解

题目

约束

题解

解法一


class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};

解法二


class Solution {
public:
    vector<vector<long long>> multiply(vector<vector<long long>> &a, vector<vector<long long>> &b) {
        vector<vector<long long>> c(2, vector<long long>(2));
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }

    vector<vector<long long>> matrixPow(vector<vector<long long>> a, int n) {
        vector<vector<long long>> ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    int climbStairs(int n) {
        vector<vector<long long>> ret = {{1, 1}, {1, 0}};
        vector<vector<long long>> res = matrixPow(ret, n);
        return res[0][0];
    }
};

解法三



class Solution {
public:
    int climbStairs(int n) {
        double sqrt5 = sqrt(5);
        double fibn = pow((1 + sqrt5) / 2, n + 1) - pow((1 - sqrt5) / 2, n + 1);
        return (int)round(fibn / sqrt5);
    }
};

标签:爬楼梯,int,ret,vector,sqrt5,70,return,public,dp
From: https://www.cnblogs.com/chuixulvcao/p/17155702.html

相关文章

  • 规则LDPC和不规则LDPC译码算法MATLAB仿真
    up目录一、理论基础二、核心程序三、测试结果一、理论基础LDPC码是根据低密度稀疏校验矩阵H来构造的。假设需要发送一组信息T{t_1,t_2,⋯,t_n},在发送前先使用生成矩......
  • python实现客户端和服务端的UDP相互通信
    实验指南这篇博客旨在实验客户端和服务端相互发送消息的实验,实验成功的现象为,客户端和服务端的两个窗口,即client和server左上角均被打上文字,因为客户端是没有给图片附上文......
  • 动态规划DP
    前言:因为在练习算法题时遇到了经典的背包问题,而解决这个问题的最优方法是动态规划为了更多的了解动态规划,结合网上资料和个人理解系统地整理了一份资料可能对于部分人......
  • m基于FPGA的NBDP系统ARQ单元模块的verilog实现
    1.算法描述       NBDP(窄带直接印字电报),全称Narrow-BandDirect-Printing。是GMDSS地面无线民系统中的一种重要通信技术,这个终端设备,要与MF、HF设备联接使用。 ......
  • 拯救者R7000 Legion 3.5mm耳机插入后有电流声,解决方法
    Intel网卡:电源策略:从最高到中高AMD游戏本——MediaTech网卡:调Realtek声卡,多流模式改经典模式......
  • 嵌入式5M570ZF256C5N, 5M570ZM100I5N(CPLD)5M570ZT100C5N设计用于低功耗应用
    MAXV设备系列的特点:低成本、低功耗、非易失性CPLD架构即时启动(0.5ms或更短)配置时间待机电流低至25µA,快速下电/复位操作快速传播延迟和时钟到输出时间内部振荡器模拟RS......
  • 2572. 无平方子集计数(状态压缩dp)
    题目https://leetcode.cn/problems/count-the-number-of-square-free-subsets/思路类似01背包优化的状态压缩dp(误)首先按照数字分出是否有平方子集,然后再计数cnt[x]......
  • P8707 [蓝桥杯 2020 省 AB1] 走方格
    题目传送门题目大意现在有个人站在第\(1\)行第\(1\)列,要走到第\(n\)行第\(m\)列(只能向右或者向下走),如果行号和列数都是偶数,不能走入这一格中。问有多少种方案。......
  • P8709 [蓝桥杯 2020 省 A1] 超级胶水
    题目传送门题目大意有\(n\)个石子,两颗石子的重量之和就是并成的一颗新石子的重量,合并两个石子需要的胶水等于两颗石子重量的乘积。解题思路先将\(sum\)赋为第一个......
  • TCP/UDP
    TCP与UDP在后台都用到套接字Socket,当准确度要求高的时候,用TCP。若追求性能和速度,而且对准确度要求不高时,用UDP。TCP协议和UDP协议连接过程的区别如下:基于连接与无连接;......