사칙연산

 

class Solution {
    static int[][] minDp;
    static int[][] maxDp;
    static int N;
    public int solution(String arr[]) {
        N = (arr.length/2)+1; //피연산자 개수
        minDp = new int[N][N];
        maxDp = new int[N][N];
        
        for(int i=N-1; i>=0; i--){
            for(int j=0; j<N; j++){
                if(i==j) { //피연산자 저장
                    maxDp[i][j] = minDp[i][j] = Integer.parseInt(arr[i*2]);
                }else{ 
                    maxDp[i][j] = Integer.MIN_VALUE; //초기화
                    minDp[i][j] = Integer.MAX_VALUE; //초기화
                    
                    for(int k=i; k<j; k++){ //i~j까지 계산
                        if(arr[2*k+1].equals("+")){
                            minDp[i][j] = Math.min(minDp[i][j],minDp[i][k]+minDp[k+1][j]);
                            maxDp[i][j] = Math.max(maxDp[i][j],maxDp[i][k]+maxDp[k+1][j]);
                        }else{ //'-' 경우
                            minDp[i][j] = Math.min(minDp[i][j],minDp[i][k]-maxDp[k+1][j]);
                            maxDp[i][j] = Math.max(maxDp[i][j],maxDp[i][k]-minDp[k+1][j]);
                        }
                    }
                }
            }
        }
        
        return maxDp[0][N-1];
    }
}

 

최댓값을 구하는 문제

=>최대가 나오기 위해선

+의 경우: 최대 + 최대

-의 경우: 최대 - 최소

 

따라서 최대, 최소를 다루는 각 dp 만들어주고

피연산자를 저장한다.

그외 부분은 정수 최소값, 최대값으로 초기화해준다.

 

완벽히 이해하고 싶다 아아아아아아 🥲