118. Pascal's Triangle

[문제 접근법]

- 양쪽 대각선은 다 1이고, 그 외 나머지 값은 윗 줄에서 하나씩 더해서 내려온다는 것을 알 수 있다.

따라서, 점화식을 세워서 증명하고 그 증명한 점화식이 맞으면 구현을 한다.

 점화식 : F[i][j] = F [i-1][j] + F [i-1][j-1] (단, i=0 || i == J일 때 제외)

 

그림 1- 파스칼 삼각형 설명

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

Pascal's Triangle - LeetCode

 

---

[구현1]

 - F [i][j] = F [i-1][j] + F [i-1][j-1] (단, i=0 || i == J일 때 제외)라는 점화식을 통해 문제를 해결하였다.

 

class Solution {
    public List<List<Integer>> generate(int numRows) {
   List<List<Integer>> list = new ArrayList<>();
        List<Integer> cur = null,prev=null;
        
        for (int i = 0; i < numRows; ++i) {
            cur = new ArrayList<>();

            for (int j = 0; j <= i; ++j) {
                if (j == 0 || i == j)
                    cur.add(1);

                else
                    cur.add(prev.get(j) + prev.get(j - 1));
            }

            prev=cur;
            list.add(cur);
            
        }

        return list;
    }
}