[LeetCode] 2684. Maximum Number of Moves in a Grid

https://leetcode.com/problems/maximum-number-of-moves-in-a-grid/?envType=daily-question&envId=2024-10-29

leetcode - Maximum Number of Moves in a Grid

문제 유형: 다이나믹 프로그래밍, 재귀, dfs, 행렬

문제 난이도: Medium

 

문제

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.

 

0-indexed의 m x n행렬 matrix가 주어진다.

matrix에서 첫 번째 컬럼 어디서든 시작해도 된다.

그리고 다음과 같이 순회하라:

(row, col)에서 유효한 (row-1, col+1), (row, col+1), (row+1, col+1)로 이동할 수 있다.

 

최대한 뻗을 수 있는 거리를 구하시오.

 

풀이

dp[row][col] = (row, col)에서 갈 수 있는 최대 거리로 저장하기로 한다.

만약 재귀함수에서 col이 m-1에 도달했다면, 순회 끝으로, 0을 반환한다.

dp에 값이 있다면, 그걸 반환한다.

그게 아니라면, 다음 유효한 칸으로 이동하기 위해 (row-1, col+1), (row, col+1), (row+1, col+1)를 호출하고 그중 가장 큰 값을 dp[row][col]에 저장한다.

 

각 열마다 한 번씩 실행한다.

 

m x n의 행렬을 한 번씩 모두 순회하여, O(m x n)의 시간복잡도, dp에 의해 O(m x n)의 공간복잡도를 갖는다.

 

코드

C++

class Solution {
private:
    int n, m;
    vector<vector<int>> dp;
    int solve(int row, int col, vector<vector<int>>& grid) {
        if(col == m-1) return 0;
        if(dp[row][col] != -1) return dp[row][col];

        int res = 0;
        for(int i = max(row-1, 0); i < min(row+2, n); ++i) {
            if(grid[row][col] < grid[i][col+1]) res = max(res, solve(i, col+1, grid) + 1);
        }
        return dp[row][col] = res;
    }
public:
    int maxMoves(vector<vector<int>>& grid) {
        n = grid.size();
        m = grid[0].size();
        int ans = 0;
        dp.resize(n, vector<int>(m, -1));
        for(int i = 0; i < n; ++i) {
            ans = max(ans, solve(i, 0, grid));
        }

        return ans;
    }
};