Leetcode#70. Climbing Stairs(爬楼梯)
发布时间:2020-12-14 03:46:34 所属栏目:大数据 来源:网络整理
导读:题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1: 输入: 2输出: 2解释: 有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶 示例 2: 输入:
题目描述假设你正在爬楼梯。需要 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 阶 思路思路一: 递归 思路二: 用迭代的方法,用两个变量记录f(n-1) f(n-2) 代码实现package DynamicProgramming; /** * 70. Climbing Stairs(爬楼梯) * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? */ public class Solution70 { public static void main(String[] args) { Solution70 solution70 = new Solution70(); System.out.println(solution70.climbStairs(3)); } /** * 直接用递归 * * @param n * @return */ public int climbStairs(int n) { if (n <= 2) { return n; } else { return climbStairs(n - 1) + climbStairs(n - 2); } } /** * 用迭代的方法,用两个变量记录f(n-1) f(n-2) * * @param n * @return */ public int climbStairs_2(int n) { int one = 1,two = 2,fN = 0; if (n <= 0) { return 0; } else if (n <= 2) { return n; } else { for (int i = 3; i <= n; i++) { fN = one + two; one = two; two = fN; } return fN; } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |