[Dynamic Programming] #118 Pascal's Triangle

<전체 Code>

class Solution(object):
    def generate(self, numRows):
        Pt = [[1]]
        for i in range(2,numRows+1):
            now = [0 for k in range(i)]
            for j in range(i):
                if j == 0 or j == i-1:
                    now[j] = 1
                else:
                    now[j] = Pt[i-2][j-1]+Pt[i-2][j]
            Pt.append(now)
        return Pt

시간 복잡도: O(N^2)

Pt의 이전 항들을 이용한 연산으로 다음 항을 구하는 방법이다. 이전 Row를 Pt에 저장해놓고 다음 row를 계산할 때 사용하는 Dynamic Programming 문제이다.