118. Pascal's Triangle

행의 수가 주어졌을 때 그 행의 길이만큼 파스칼의 삼각형을 만들어라.

파스칼의 삼각형은 각 수가 직전 수의 합으로 만들어진다.

 

 

---

 

solution 1.

직전 수의 합은 인덱스로 본다면,

직전행의 동일한 인덱스의 수 더하기 직전행의 하나 작은 인덱스의 수를 더해서 해당 수가 만들어진다.

 

그리고 처음의 수와 마지막 수는 없는 수 더하기 1의 연속이므로 계속 1로 유지된다.

그렇기 때문에 처음과 마지막이 1로 유지될 수 있게 하는 방법도 필요하다.

 

그리고 시작의 수가 1이라는 점도 잊지 말아야 한다.

그렇기 때문에 1로 모든 행을 초기화 해놓고 첫 열과 마지막 열을 1로 초기화 할 수 있다.

그 후, 직전행의 동일한 인덱스의 수 더하기 직전행의 하나 작은 인덱스의 수를 더하면 해당 행의 수가 만들어지게 한다.

 

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        out = []
        for i in range(numRows):
            out.append([1]*(i+1))

        for i in range(numRows):
            for j in range(1, i):
                out[i][j] = out[i-1][j-1] + out[i-1][j]
        return out