leetcode#70 Climbing Stairs

1. 문제

• https://leetcode.com/problems/climbing-stairs/
  

2. 나의 풀이

2-1. Time Limit Exceeded

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        finish_result = []
        result = [[1],[2]]
        
        
        count = 0
        while count < n:
            new_result = []
            while len(result) > 0:
                # print("haha", finish_result, result)
                temp = result.pop()
                if sum(temp) == n:
                    finish_result.append(temp)
                    continue
                if sum(temp) > n:
                    continue
                
                new_result.append(temp+[1])
                new_result.append(temp+[2])
                # print("new+result", new_result)
            result = new_result
            count += 1
        
        # print("finish result", finish_result)
        return len(finish_result)

2-2.

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        finish_result = []
        result = [1, 2]
        
        
        count = 0
        while count < n:
            new_result = []
            while len(result) > 0:
                # print("haha", finish_result, result)
                temp = result.pop()
                if temp == n:
                    finish_result.append(temp)
                    continue
                    
                if (temp + 1) == n:
                    finish_result.append(temp+1)
                    
                if (temp + 2) == n:
                    finish_result.append(temp+2)
                
                if (temp + 1) < n:
                    new_result.append(temp+1)
                    
                if (temp + 2) < n:
                    new_result.append(temp+2)
            
            result = new_result
            count += 1
        
        # print("finish result", finish_result)
        return len(finish_result)
        

2-3. 재귀호출

class Solution(object):
    

    
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        memory = {}
        
        def countN(n):
            # print(n, memory)
            if n < 0:
                return 0
            if n == 0:
                return 1

            if memory.get(n):
                return memory.get(n)

            # print(n)
            memory[n] = countN(n-1) + countN(n-2)

            return memory.get(n)
        
        return countN(n)

3. 남의 풀이