爬楼梯(LeetCode-70)

简介: 爬楼梯(LeetCode-70)

2. 爬楼梯(LeetCode-70)


题目

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


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


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


示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶


示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶


思路

第⼀层楼梯再跨两步就到第三层 ,第⼆层楼梯再跨⼀步就到第三层。 所以到第三层楼梯的状态可以由第⼆层楼梯和到第⼀层楼梯状态推导出来


五部曲


dp[i] 定义:爬到第 i 阶有 dp[i] 种方法

d p [ i ] = d p [ i − 2 ] + d p [ i − 1 ]

dp[1]=1 dp[2]=2 正整数不用考虑 dp[0]

肯定从前往后

前五项 1 2 3 5 8


代码展示

class Solution
{
public:
    int climbStairs(int n)
    {
        // 这步忘记了,导致n=1时访问不到dp[2]
        if (n<=1)
        {
            return n;
        }  
        vector<int> dp(n + 1);
        dp[1] = 1, dp[2] = 2;
        for (int i = 3; i <= n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
            cout << dp[i];
        }
        return dp[n];
    }
};


也是可以优化,滚动数组优化空间

class Solution
{
public:
    int climbStairs(int n)
    {
        if (n <= 2)
        {
            return n;
        }
        vector<int> dp(3);
        dp[1] = 1, dp[2] = 2;
        int result;
        for (int i = 3; i <= n; i++)
        {
            result = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = result;
        }
        return result;
    }
};
目录
相关文章
|
11月前
|
机器学习/深度学习 人工智能 并行计算
"震撼!CLIP模型:OpenAI的跨模态奇迹,让图像与文字共舞,解锁AI理解新纪元!"
【10月更文挑战第14天】CLIP是由OpenAI在2021年推出的一种图像和文本联合表示学习模型,通过对比学习方法预训练,能有效理解图像与文本的关系。该模型由图像编码器和文本编码器组成,分别处理图像和文本数据,通过共享向量空间实现信息融合。CLIP利用大规模图像-文本对数据集进行训练,能够实现zero-shot图像分类、文本-图像检索等多种任务,展现出强大的跨模态理解能力。
1121 2
|
设计模式 缓存 前端开发
深入理解 Netty编码流程及WriteAndFlush()的实现 (一)
深入理解 Netty编码流程及WriteAndFlush()的实现 (一)
587 0
No module factory available for dependency type: ModuleHotAcceptDependency
No module factory available for dependency type: ModuleHotAcceptDependency
444 0
|
人工智能 开发者
如何防止AI技术被滥用?
【6月更文挑战第1天】如何防止AI技术被滥用?
485 4
|
机器学习/深度学习 人工智能 自然语言处理
人工智能(AI)技术的发展史
人工智能 (AI) 的发展历程从20世纪50年代起步,历经初始探索、早期发展、专家系统兴起、机器学习崛起直至深度学习革命。1950年图灵测试提出,1956年达特茅斯会议标志着AI研究开端。60-70年代AI虽取得初步成果但仍遭遇困境。80年代专家系统如MYCIN展现AI应用潜力。90年代机器学习突飞猛进,1997年深蓝战胜国际象棋冠军。21世纪以来,深度学习技术革新了AI,在图像、语音识别等领域取得重大成就。尽管AI已广泛应用,但仍面临数据隐私、伦理等挑战。未来AI将加强人机协作、增强学习与情感智能,并在医疗、教育等领域发挥更大作用。
|
Java
JAVA 端口被占用 报错解决方案:java.net.BindException: Address already in use: bind
JAVA 端口被占用 报错解决方案:java.net.BindException: Address already in use: bind
710 0
java.net.BindException: Address already in use: 解决方法
java.net.BindException: Address already in use: 解决方法
1219 0
|
XML Android开发 数据格式
Android Glide加载网络图片不显示,但用网页打开又正常显示
Android Glide加载网络图片不显示,但用网页打开又正常显示
1046 0
Android Glide加载网络图片不显示,但用网页打开又正常显示
|
Java Spring 容器
Spring中用于装配组件的常见扩展点的介绍
在Spring的项目中,组件的组装离不开Spring提供的一些扩展点,本文对BeanFactoryPostProcessor、FactoryBean、BeanPostProcessor、@Import这四个扩展点做了简单的介绍。
199 4