Go Gradually - Repository

1301. Number of Paths with Max Score - Streak 6

DP 로 최댓값을 유지하면 풀 수 있다. 근거: 해당 지점의 최댓값이 바뀌면, 이후는 반드시 그 최댓값 경로를 따라야 한다.따라서, 비교적 간단하게 최적 부분 구조+중복 부분문제를 만족한다. 그럼 남은 문제는, "벽 의 처리를 어떻게 할 것인가?"이다.그냥 초깃값을 매우 낮은 음수로 설정해두면 된다.1만 * 9 = 최대 값 9만이니, 기본 값 초기화를 전부 -10억으로 해두면 벽을 뛰어넘는 값으로 잘못된 값을 리턴하기 어려워진다.class Solution { public int[] pathsWithMaxScore(List board) { int n = board.size(); List> dp = new ArrayList(); for(int i = 0; i tem..

내 풀이 접근현재 인덱스까지 구할 수 있는 최대 수익을 계산하려면이전 인덱스에 담겨 있는 최대 수익과, 그 인덱스부터 지금까지의 1회 최대 수익을 알고 있어야 한다.이는 카데인 알고리즘과 굉장히 유사하다고 판단했다. 따라서 DP를 이용해 현재 인덱스까지 가장 최적의 이익을 찾도록 했다.class Solution { public int maxProfit(int k, int[] prices) { int[][] dp = new int[prices.length + 1][k+1]; int ret = 0; for(int kk = 1; kk이래도 통과는 한다.하지만, 조건이 빡빡하다면 통과하지 못했을 것이다.좀 더 효율적인 해이전에 구할 수 있는 최대 이익을, 0~i까지 전..