解決策:境界パス外

これは一連のleetcode解決説明の一部です.あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストとmy solution post on Leetcode's forums .

Leetcode問題は、1つの境界パス

説明

にジャンプします.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］)は、Dが移動の数であり、IとJが開始位置の座標であるというDP行列を作成することができる.d = 1からd = maxmoveまでこのDP行列を構築することができます.
DPを構築するには、D = 1のときに開始値を入力することによって開始することができます.そこから、私たちはDのために残りの値を通して反復することができます、そして、各々のセルは前の移動反復(D - 1)からの周囲の4つのセルの合計であるでしょう.
私たちが完全なmaxmoveをとらないどんな経路も含めたいので、解決(ANS)はそれからD =のためにすべての可能な値でi = startrowとj = startcolumnに対応するDPのセルの合計です.
境界チェックの必要性を防ぐことによって容易にするために、我々は0の値で満たされるDPのグリッド表現のすべての4つの側にバッファ行/コラムを加えることができます.
我々が現在のものを構築するためにDの以前の反復を使うだけで、我々はMaxLove深さの3 D行列の代わりに2つの2 Dマトリックス(DPCurr、DPLast)だけにDPを圧縮することによって、この解決でスペースを節約することができます.これを行うには、各繰り返しの間にdpcurrとdplastをスワップし、それを繰り返すとDPcurrの古い値を上書きするだけで行うことができます.我々はまた、我々は行くようにアンを追跡することができます.
また、各セル値式でモジュロ演算を使用することを忘れてはいけません.

時間複雑さ:n(n)は格子の次元であり、lは移動の最大数である

空間複雑度DP行列のO(n＊m)

JavaScriptコード

にジャンプします.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
};

Pythonコード:

にジャンプします.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

Javaコード:

にジャンプします.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;
    }
};