1301. Number of Paths with Max Score - Streak 6

 

DP 로 최댓값을 유지하면 풀 수 있다.

 

근거: 해당 지점의 최댓값이 바뀌면, 이후는 반드시 그 최댓값 경로를 따라야 한다.
따라서, 비교적 간단하게 최적 부분 구조+중복 부분문제를 만족한다.

 

그럼 남은 문제는, "벽 의 처리를 어떻게 할 것인가?"이다.

그냥 초깃값을 매우 낮은 음수로 설정해두면 된다.
1만 * 9 = 최대 값 9만이니, 기본 값 초기화를 전부 -10억으로 해두면 벽을 뛰어넘는 값으로 잘못된 값을 리턴하기 어려워진다.

class Solution {

    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        List<List<Pair>> dp = new ArrayList<>();
        for(int i = 0; i<n; i++){
            List<Pair> temp = new ArrayList<>();
            for(int j = 0; j<n; j++){
                temp.add(new Pair(-100000000, 0));
            }
            dp.add(temp);
        }
        dp.get(n-1).set(n-1, new Pair(0, 1));
        dp.get(0).set(0, new Pair(0, 0));

        for(int i = n-1; i>= 0; i--){
            for(int j = n-1; j >= 0; j--){
                char nowChar = board.get(i).charAt(j);
                if(nowChar == 'X') {
                    dp.get(i).set(j, new Pair(-1000000000, 0));
                    continue;
                }
                if(nowChar == 'S' || nowChar == 'E') nowChar = '0';
                int now = nowChar - '0';

                if (i + 1 < n){
                    set(i, j, i+1, j, now, board, dp);
                }

                if (j + 1 < n){
                    set(i, j, i, j+1, now, board, dp);
                }

                if(i + 1 < n && j + 1 < n){
                    set(i, j, i+1, j+1, now, board, dp);
                }
            }
        }
        Pair result = dp.get(0).get(0);
        return new int[]{result.value, (int) result.count};
    }

    private void set(int i, int j,int k, int l, int now, List<String> board, List<List<Pair>> dp){

        long MOD = 1000000007L;
        char beforeChar = board.get(k).charAt(l);
        if(beforeChar!='X'){
            Pair nowPair = dp.get(i).get(j);
            Pair beforePair = dp.get(k).get(l);
            if(nowPair.value < beforePair.value + now){
                dp.get(i).set(j, new Pair(beforePair.value + now, beforePair.count));
            }else if (nowPair.value == beforePair.value + now){
                dp.get(i).set(j, new Pair(nowPair.value, (nowPair.count + beforePair.count) % MOD));
            }
        }
    }
}

public class Pair {
    public int value;
    public long count;
    public Pair(int a, long b){
        this.value = a;
        this.count = b;
    }
}