솔루션: 경계를 벗어난 경로

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 들었거나 유용하다고 생각되면 이 게시물에 좋아요를 누르거나 찬성 투표my solution post on Leetcode's forums를 해주세요.

Leetcode 문제 #576(중간): 경계를 벗어난 경로

설명:

(다음으로 이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent four cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.

예:

Example 1:
Input:	m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output:	6
Visual:

Example 2:
Input:	m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output:	12
Visual:

제약:

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow <= m
• 0 <= startColumn <= n

아이디어:

(다음으로 이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

가능한 경로의 수가 4^maxMove이기 때문에 이 문제에 대한 무차별 대입 솔루션은 너무 길 것입니다. 겹치는 경로를 포함하는 대부분의 문제의 경우와 마찬가지로 이 문제는 동적 프로그래밍(DP) 접근 방식의 도움으로 이러한 겹치는 경로를 결합하여 단순화할 수 있습니다.

이 경우 각 셀(dp[d][i][j])이 솔루션을 나타내는 DP 행렬을 만들 수 있습니다. 여기서 d는 남은 이동 횟수이고 i와 j는 시작 위치의 좌표입니다. 그런 다음 d = 1에서 d = maxMove까지 이 DP 행렬을 만들 수 있습니다.

dp를 구축하기 위해 d = 1일 때 시작 값을 채우는 것으로 시작할 수 있습니다. 이때 가장자리를 따라 있는 각 셀은 1이고 각 모서리는 2입니다. 거기에서 나머지 값을 통해 반복할 수 있습니다. d, 각 셀은 이전 이동 반복(d-1)에서 주변 4개 셀의 합이 됩니다. 이러한 셀은 현재 셀로 이동하기 전에 가능한 이전 위치에 해당하기 때문입니다.

전체 maxMove를 차지하지 않는 경로를 포함하기를 원하므로 솔루션(ans)은 i = startRow 및 j = startColumn에 해당하는 dp의 셀과 d에 대한 모든 가능한 값의 합이 됩니다.

범위를 벗어난 검사의 필요성을 방지하여 작업을 더 쉽게 하기 위해 0 값으로 채워진 dp의 그리드 표현의 4면 모두에 버퍼 행/열을 추가할 수 있습니다.

우리는 d의 이전 반복을 사용하여 현재 반복을 만들기만 하므로 maxMove 깊이의 3D 행렬 대신 dp를 두 개의 2D 행렬(dpCurr, dpLast)로만 압축하여 이 솔루션의 공간을 절약할 수 있습니다. 각 반복 사이에 dpCurr 및 dpLast를 교체하고 반복하면서 dpCurr의 이전 값을 덮어쓰면 됩니다. 그런 다음 이동하면서 ans를 추적할 수도 있습니다.

또한 각 셀 값 방정식에 모듈로 연산을 사용하는 것을 잊지 말아야 합니다.

시간 복잡도: O(N * M * L) 여기서 N과 M은 그리드의 크기이고 L은 최대 이동 수입니다

.

공간 복잡도: DP 행렬의 경우 O(N * M)

자바스크립트 코드:

(다음으로 이동: Problem Description || Solution Idea )

var findPaths = function(m, n, maxMove, startRow, startColumn) {
    if (!maxMove) return 0
    let dpCurr = Array.from({length: m+2}, () => new Uint32Array(n+2)),
        dpLast = Array.from({length: m+2}, () => new Uint32Array(n+2))
    for (let i = 1; i <= m; i++)
        dpCurr[i][1]++, dpCurr[i][n]++
    for (let j = 1; j <= n; j++)
        dpCurr[1][j]++, dpCurr[m][j]++
    let ans = dpCurr[startRow+1][startColumn+1]
    for (let d = 1; d < maxMove; d++) {
        [dpCurr, dpLast] = [dpLast, dpCurr]
        for (let i = 1; i <= m; i++)
            for (let j = 1; j <= n; j++)
                dpCurr[i][j] = (dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007
        ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007
    }
    return ans
};

파이썬 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        if maxMove == 0: return 0
        dpCurr = [[0] * (n+2) for _ in range(m+2)]
        dpLast = [[0] * (n+2) for _ in range(m+2)]
        for i in range(1, m+1):
            dpCurr[i][1] += 1
            dpCurr[i][n] += 1
        for j in range(1, n+1):
            dpCurr[1][j] += 1
            dpCurr[m][j] += 1
        ans = dpCurr[startRow+1][startColumn+1]
        for d in range(maxMove-1):
            dpCurr, dpLast = dpLast, dpCurr
            for i, j in product(range(1, m+1), range(1, n+1)):
                dpCurr[i][j] = (dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007
        return ans

자바 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) return 0;
        int[][] dpCurr = new int[m+2][n+2], dpLast = new int[m+2][n+2];
        for (int i = 1; i <= m; i++) {
            dpCurr[i][1]++;
            dpCurr[i][n]++;
        }
        for (int j = 1; j <= n; j++) {
            dpCurr[1][j]++;
            dpCurr[m][j]++;
        }
        int ans = dpCurr[startRow+1][startColumn+1];
        for (int d = 1; d < maxMove; d++) {
            int[][] temp = dpCurr;
            dpCurr = dpLast;
            dpLast = temp;
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dpCurr[i][j] = (int)(((long)dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007L);
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007;
        }
        return ans;
    }
}

C++ 코드:

(다음으로 이동: Problem Description || Solution Idea )

class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (!maxMove) return 0;
        vector<vector<int>> dpCurr(m+2, vector<int>(n+2)),
            dpLast(m+2, vector<int>(n+2));
        for (int i = 1; i <= m; i++)
            dpCurr[i][1]++, dpCurr[i][n]++;
        for (int j = 1; j <= n; j++)
            dpCurr[1][j]++, dpCurr[m][j]++;
        int ans = dpCurr[startRow+1][startColumn+1];
        for (int d = 1; d < maxMove; d++) {
            dpCurr.swap(dpLast);
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dpCurr[i][j] = (int)(((long)dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007L);
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007;
        }
        return ans;
    }
};