leetcode 64 java dp

/*
**m x n 크기의 그리드(grid)**가 주어졌으며, 각 칸에는 0 이상의 숫자가 들어 있습니다.

왼쪽 상단 **(grid[0][0])**에서 오른쪽 하단 **(grid[m-1][n-1])**으로 이동하는 경로 중에서,
경로 상의 숫자 합이 최소가 되는 경로를 찾으세요.

📌 제한 사항:

한 번에 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.
*/

class Solution {
    public int minPathSum(int[][] grid) {
        int y = grid.length;
        int x = grid[0].length;

        int [][] dp = new int[y][x];

        dp[0][0] = grid[0][0];
        for(int i=1; i<x; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int j=1; j<y; j++) {
            dp[j][0] = dp[j-1][0] + grid[j][0];
        }

        for(int j=1; j<y; j++) {
            for(int i=1; i<x; i++) {
                dp[j][i] = Math.min(dp[j-1][i], dp[j][i-1]) + grid[j][i];
            }
        }

        return dp[y-1][x-1];
    }
}

 

 

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

 

 

일단 최종구역까지 어느 구간이 최단거리인지 찾는 문제이다. dp 는 2차원 배열이 필요하다.

 

1열과 1행은 누적된 값을 넣어준다.

 

해당그림에서의 dp는

1  4  5

2  0  0

6  0  0

으로 초기화가 되고 dp 순차탐색이 시작된다.

점화식은 다음과 같다.

 

dp[j][i] = Math.min(dp[j-1][i], dp[j][i-1]) + grid[j][i];

 

현재 기준으로 위와 왼쪽중에 최단거리를 찾아 grid[i][j](현재값) 을 더하면 현재 위치까지의 최단 거리가 나온다.

 

그렇게 끝까지 진행하고 리턴하면 정답이 나온다.

 

최종 dp 값은 이렇다.

 

1  4  5

2  7  6

6  8  7

 

따라서 7이 정답이다.