[LeetCode] 118. Pascal's Triangle | LIM

문제

https://leetcode.com/problems/pascals-triangle/description/

Pascal's Triangle - LeetCode

 

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

 

Example1

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

 

Example2

Input: numRows = 1
Output: [[1]]

 

 

설명

대표적인 DP 문제로 점화식을 잘 정의하면 쉽게 풀 수 있는 문제이다. 왼쪽위와 오른쪽위의 숫자를 더한값이 현재 숫자가 되는 것이다. 이를 점화식으로 표현하면 다음과 같다. 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

 

푼 순서

1. 길이가 증가하는 배열을 만들고 원소는 1로 초기화한다.

2. 자신의 왼쪽위와 오른쪽 위 숫자를 더해서 업데이트한다.

3. 첫번째 원소나 마지막 원소는 자신의 왼쪽 위 혹은 오른쪽 위가 없기 때문에 그대로 1이 된다. 

 

코드

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp = [[1] * i for i in range(1, numRows+1)]
        for i in range(2, numRows):
            for j in range(1, len(dp[i])-1):
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        return dp

 

결과

 

Solution 보는데 누군가 O(1) 로 풀었다고 해서 오 뭐지 이러면서 찾아봤는데 풀이보고 빵터졌다..🤣

 

https://leetcode.com/problems/pascals-triangle/solutions/2301657/simple-o-1-solution-in-python/

Simple O(1) solution in Python - Pascal's Triangle - LeetCode

 

Runtime 은 확실히 좋고 Memeory 도 내 코드랑 동일했다..ㅋㅋ