您的位置:首页 > 科技 > IT业 > 88黄页网发帖效果好吗_今日大事件新闻_微信引流用什么软件好用_企业网站设计毕业论文

88黄页网发帖效果好吗_今日大事件新闻_微信引流用什么软件好用_企业网站设计毕业论文

2024/12/23 11:00:50 来源:https://blog.csdn.net/lvhao123456789/article/details/142631030  浏览:    关键词:88黄页网发帖效果好吗_今日大事件新闻_微信引流用什么软件好用_企业网站设计毕业论文
88黄页网发帖效果好吗_今日大事件新闻_微信引流用什么软件好用_企业网站设计毕业论文

文章目录

  • 题目描述
  • 解题方法
    • 动态规划
      • java代码
      • 复杂度分析

题目描述

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= n <= 45

解题方法

动态规划

这道题目求解符合斐波那契数列的特点。当我们爬到第n阶楼梯时,最后一步一共有两种情况,要么从第n - 1阶楼梯迈1步,要么从第n - 2阶楼梯迈2步;所以爬到第n阶楼梯的方法数等于爬到第n - 1阶楼梯的方法数加上爬到第n - 2阶楼梯的方法数。
我们可以总结出如下规律,设 f ( n ) f(n) f(n)为爬到第n阶楼梯的方法数,则:

  • n = 0 n = 0 n=0时, f ( 0 ) = 1 f(0) = 1 f(0)=1
  • n = 1 n = 1 n=1时, f ( 1 ) = 1 f(1) = 1 f(1)=1
  • n > 1 n > 1 n>1时, f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2) f(n)=f(n1)+f(n2)

根据规律使用动态规划即可求解。

java代码

public int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 2] + dp[i - 1];}return dp[n];
}

复杂度分析

  • 时间复杂度: O ( N ) O(N) O(N)
  • 空间复杂度: O ( N ) O(N) O(N)

  • 个人小游戏
    个人小游戏
    在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com