leetCode (Pascal's Triangle) - Array, DP

문제

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:

 

Example 1:

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

 

---

배경지식

1. Array - 메모리 상에 원소를 연속하게 배치한 자료구조

2. DP - 여러개의 하위 문제를 먼저 풀고, 그것을 쌓아올려 주어진 문제를 해결하는 알고리즘

 

문제해결

1.테이블 설계
	DP[i][j]는 바로 위의 인접한 두 개의 숫자의 합니다
    
2.점화식 세우기
	DP[i][j] = DP[i-1][j] + DP[i-1][j-1]
    
3.초기값 설정
	DP[0][0] = 1
	DP[1][0] = 1
	DP[1][1] = 1

 

구현

const generate = function (numRows) {
    if (numRows <= 0) {
        return []
    }
    let dp = [[1]];
    for (let i = 1; i < numRows; i++) {
        dp[i] = [];
        dp[i].push(1);
        for (let j = 1; j <= i - 1; j++) {
            dp[i].push(dp[i - 1][j] + dp[i - 1][j - 1])
        }
        dp[i].push(1)
    }
    return dp;
};