2024 10 29 2684. Maximum Number of Moves in a Grid

문제

You are given a 0-indexed m x n matrix grid consisting of positive integers.

You can start at any cell in the first column of the matrix, and traverse the grid in the following way:

From a cell (row, col), you can move to any of the cells: (row - 1, col + 1), (row, col + 1) and (row + 1, col + 1) such that the value of the cell you move to, should be strictly bigger than the value of the current cell.
Return the maximum number of moves that you can perform.

요약

첫 열에서 시작해서 오른쪽으로 위 옆 아래에 더 큰 숫자로 움직일수 있다.

이때 최대 이동 횟수를 나타내면된다

풀이

dfs로 움직임 횟수를 가져오되 각 자리에서 그 뒤에 최대로 움직인 횟수를 저장해주면된다.

만약 0이 아닐 경우 항상 최대 움직임 수 이므로 이 수를 걍 반환하면 된다.

코드

class Solution {

    private static final int[] R_DIR = {-1,0,1};

    public int maxMoves(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        int result = 0;
        for (int r = 0; r < grid.length ; r ++) {
            result = Math.max(dfs(r, 0, dp, grid) - 1, result);
        }
        return result;
    }

    private int dfs(int r, int c, int[][] dp, int[][] grid) {
        if (dp[r][c] != 0) {
            return dp[r][c];
        }
        int up = 0;
        int right = 0;
        int down = 0;
        if (r - 1 >= 0 && c + 1 < dp[0].length && grid[r][c] < grid[r -1][c + 1]) {
            up = dfs(r - 1, c + 1, dp, grid);
        }
        if (c + 1 < dp[0].length && grid[r][c] < grid[r][c + 1]) {
            right = dfs(r, c + 1, dp, grid);
        }
        if (r + 1 < dp.length && c + 1 < dp[0].length && grid[r][c] < grid[r + 1][c + 1]) {
            down = dfs(r + 1, c + 1, dp, grid);
        }
        int max = Math.max(up, Math.max(right, down));
        dp[r][c] = max;
        return max + 1;
    }
}

풀이 시간

10분

체감 난이도

easy