[Programmers:DP] 사칙연산

❓문제

괄호를 어디에 치느냐에 따라 결과가 달라짐 -> 이 결과들 중 최솟값을 Return

---

🖐️손코딩

dpMax[i][j] : i번째 숫자부터 j번째 숫자까지 만들 수 있는 최댓값
dpMin[i][j] : i번째 숫자부터 j번째 숫자까지 만들 수 있는 최솟값

i~j의 중간 인덱스 : k

k == '+' : 
	Max = leftMax + rightMax
    Min = leftMin + rightMin
k == '-' :
	Max = leftMax - rightMin
    Min = leftMin - rightMax
    
 return dpMin[0][n-1]

구간 DP는 구간 길이를 기준으로 범위 지정해야함!

---

👩‍💻구현 코드

import java.util.*;

class Solution {
    public int solution(String arr[]) {
        int answer = -1;
        int n = 0;
        
        for(int i = 0; i<arr.length; i++){
            if(Character.isDigit(arr[i].charAt(0))){
                n++;
            }
        }
        
        int[][] dpMin = new int[n][n];
        int[][] dpMax = new int[n][n];
        
        for(int len = 1; len <= n ; len++){
            for(int i = 0; i+len-1 < n; i++){
                int j = i+len-1;
                
                if(i==j){
                    int num = Integer.parseInt(arr[i * 2]);
                    dpMin[i][j] = num;
                    dpMax[i][j] = num;
                } else {
                    dpMax[i][j] = Integer.MIN_VALUE;
                    dpMin[i][j] = Integer.MAX_VALUE;
                    
                    for(int k = i; k<j; k++){
                        String ope =  arr[k*2+1];
                        
                        if(ope.equals("+")){
                            dpMax[i][j] = Math.max(dpMax[i][j], dpMax[i][k]+dpMax[k+1][j]);
                            dpMin[i][j] = Math.min(dpMin[i][j], dpMin[i][k]+dpMin[k+1][j]);
                        } else if(ope.equals("-")){
                            dpMax[i][j] = Math.max(dpMax[i][j], dpMax[i][k]-dpMin[k+1][j]);
                            dpMin[i][j] = Math.min(dpMin[i][j], dpMin[i][k]-dpMax[k+1][j]);
                        }
                    }
                }
            }
        }
        
        answer = dpMax[0][n-1];
        
        
        return answer;
    }
}

---

https://school.programmers.co.kr/learn/courses/30/lessons/1843