.leetcode(64. Minimum Path Sum)

문제

https://leetcode.com/problems/minimum-path-sum/

문제 풀기 전

1. 이건 왠지 dp로 풀 수 있을거같다는 감은 왔다.

직접 푼 풀이

소요시간: 40분

재도전하기

느낀점

1. 결국 brute force로도 못 풀었다.
2. dp로 푸는방식이 있다. 아래와 같다. 결국 dp로 푸는것은 지금의 값을 결정하는 요소들의 비교가 아닐까 하다. 아래 푸는 방식을 보면 합해진 값의 오른쪽과 합해진 값의 아래쪽 중에 작은걸 선택해서 0,0까지 더하는 방식인데 이걸 잘 기억해두면 다음법 dp스러운 문제를 봐도 힌트가 될 것이다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public int minPathSum(int[][] grid) {
        for (int i=grid.length-1; i>=0; i--) {
            for (int j=grid[i].length-1; j>=0; j--) {
                if (i==grid.length-1 && j==grid[i].length-1) {   
                } else if (i==grid.length-1) {
                    grid[i][j] = grid[i][j]+grid[i][j+1];
                } else if (j==grid[i].length-1) {
                    grid[i][j] = grid[i][j]+grid[i+1][j];
                } else {
                    grid[i][j] = grid[i][j]+Math.min(grid[i+1][j],grid[i][j+1]);
                }
            }
        }

        return grid[0][0];
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)