有哪些网站建设工作,找外贸客户的网站,沈阳哪家公司做网站好,青岛seo排名收费目录
题目
解法
Go
Java
Python 代码地址#xff1a;leetcode: 每日leetcode刷题
题目
题号70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1#xff1a; 输入#xff…目录
题目
解法
Go
Java
Python 代码地址leetcode: 每日leetcode刷题
题目
题号70. 爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1 输入n 2 输出2 解释有两种方法可以爬到楼顶。 1. 1 阶 1 阶 2. 2 阶
示例 2 输入n 3 输出3 解释有三种方法可以爬到楼顶。 1. 1 阶 1 阶 1 阶 2. 1 阶 2 阶 3. 2 阶 1 阶
解法
Go
package mainimport fmt//方法一 递归 使用map求解出的结果不用重复求解
//满足公式
//F(1) 1
//F(2) 2
//F(n) F(n-1) F(n-2) (n2)
var mp make(map[int]int)
func climbStairs1(n int) int {if n 2 {return n}if _, ok : mp[n]; ok {return mp[n]} else {rst : climbStairs1(n-1) climbStairs1(n-2)mp[n] rstreturn rst}
}// 方法二 使用for循环用两个变量记录上次和上上次的值时间复杂度O(n)
func climbStairs(n int) int {if n 2 {return n}rst : 0pre : 2prepre : 1for i : 3; i n; i {rst pre prepreprepre prepre rst}return rst
}func main() {fmt.Println(climbStairs(7))
}
Java
package org.example;import java.util.HashMap;
import java.util.Map;public class ClimbingStairs {// 方法一 递归 使用map求解出的结果不用重复求解// 满足公式// F(1) 1// F(2) 2// F(n) F(n-1) F(n-2) (n2)private MapInteger, Integer mp new HashMapInteger, Integer();public int climbStairs1(int n) {if (n 1) {return 1;}if (n 2) {return 2;}if (null ! mp.get(n)) {return mp.get(n);} else {int val climbStairs1(n - 1) climbStairs1(n - 2);mp.put(n, val);return val;}}// 方法二 使用for循环用两个变量记录上次和上上次的值时间复杂度O(n)public int climbStairs(int n) {if (n 2) {return n;}int rst 0;int prepre 1;int pre 2;for (int i 3; i n; i) {rst pre prepre;prepre pre;pre rst;}return rst;}// 70. 爬楼梯public static void main(String[] args) {ClimbingStairs main new ClimbingStairs();System.out.println(main.climbStairs(7));}}
Python
# 方法一 递归 使用map求解出的结果不用重复求解
# 满足公式
# F(1) 1
# F(2) 2
# F(n) F(n-1) F(n-2) (n2)
dic {}
def climbStairs1(n):if n 1:return 1if n 2:return 2if n in dic:return dic[n]else:val climbStairs1(n - 1) climbStairs1(n - 2)dic[n] valreturn val# 方法二 使用for循环用两个变量记录上次和上上次的值时间复杂度O(n)
def climbStairs(n):if n 1:return 1if n 2:return 2count 0prepre 1pre 2for i in range(3, n 1):count prepre preprepre prepre countreturn countif __name__ __main__:print(climbStairs(3))
