leetcode——70.爬楼梯

 1 class Solution:
 2     def climbStairs(self, n: int) -> int:
 3         #假设爬了x次一个台阶，y个两次台阶
 4         #求x与y的组合序列
 5         if n==0:
 6             return 0
 7         m=0
 8         for x in range(n+1):
 9             #print(x)
10             for y in range(n//2+1):
11                 #print(y)
12                 if x+2*y==n:
13                     #print(x,y)
14                     if x!=0 and y!=0:
15                         t=x+y-1
16                         fenzi=x+y
17                         fenmu=1
18                         while t>y :
19                             fenzi=fenzi*t
20                             t=t-1
21                         #print(fenzi)
22                         q=x
23                         while q>0:
24                             fenmu=fenmu*q
25                             q=q-1
26                         #print(fenmu)
27                         m=m+fenzi//fenmu
28                         #print(m)
29                     else:
30                         m=m+1                
31         return m

执行用时 :40 ms, 在所有 Python3 提交中击败了93.94%的用户

内存消耗 :13.8 MB, 在所有 Python3 提交中击败了5.14%的用户

很开心！

今天做出来的第二道题。

——2019.9.27

典型动态规划

用时4分40秒

public int climbStairs(int n) {
        //使用动态规划
        //用一个数组来进行存储，或者用map来进行存储
        Map<Integer,Integer> map = new HashMap<>();
        map.put(1,1);
        map.put(2,2);
        if(map.containsKey(n)){
            return map.get(n);
        }
        for(int i = 3;i<= n;i++){
            map.put(i,map.get(i-1)+map.get(i-2));
        }
        return map.get(n);
    }

我的前方是万里征途，星辰大海！！