99클럽 코테 스터디 21일차 TIL - DP

문제

파스칼 삼각형

풀이

• numRows만큼 순회하면서 이전 배열의 j-1 + j값을 가져와서 새로운 배열을 만듦

코드 - 순회

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();
    
        for(int i = 1; i <= numRows; i++){
            List<Integer> sub = new ArrayList<>();
            sub.add(1);
            
            if(i > 2) {
                List<Integer> prev = answer.get(i - 2);
                for(int j = 1; j < i - 1; j++){
                    int val = prev.get(j - 1) + prev.get(j);
                    sub.add(val);
                }
            }
            if(i > 1){
                sub.add(1);
            }
            answer.add(sub);

        }
        return answer;
    }
}

코드 - DP

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<>();
    
        for(int i = 0; i < numRows; i++){
            List<Integer> row = new ArrayList<>(Collections.nCopies(i+1, 1));
            for(int j =1; j < i; j++){
                row.set(j, dp.get(i-1).get(j-1) + dp.get(i-1).get(j));
            }
           dp.add(row);
        }
        
        return dp;
    }
}

정리

• DP 문제인데 DP로는 도저히 못 풀겠어서 for문 사용
• 수학 베이스 문제들은 푸는데 시간이 오래 걸리는 거 같다
• DP는 아직 아닌 거 같다...