昆明品牌网站建设太原seo
问题:
假设你正在爬楼梯。需要 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，其中dp[i]表示爬到第i个台阶的不同方法数。根据题目的条件，我们知道爬到第i个台阶有两种方法：从爬到第i-1个台阶再爬1个台阶，或者从爬到第i-2个台阶再爬2个台阶。所以，我们可以得到动态规划的状态转移方程：
dp[i] = dp[i-1] + dp[i-2]
初始条件为dp[0]=1和dp[1]=1。因为爬到第0个台阶只有一种方法，就是不用爬；爬到第1个台阶也只有一种方法，就是爬一步。
根据以上思路，我们可以编写如下的Java代码来解决这个问题：
public class Solution {public int climbStairs(int n) {if(n <= 1){return 1;}int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}}在主函数中，我们可以创建一个Solution对象，并调用climbStairs方法传入楼梯的阶数n来得到结果。
public class Main {public static void main(String[] args) {Solution solution = new Solution();int n = 3;int result = solution.climbStairs(n);System.out.println(result);}}以上代码中，输入为3，输出为3，符合题目要求。
时间复杂度：O(n)，其中n为楼梯的阶数。
空间复杂度：O(n)。
(文章为作者在学习java过程中的一些个人体会总结和借鉴，如有不当、错误的地方，请各位大佬批评指正，定当努力改正，如有侵权请联系作者删帖。)