576. Out of Boundary Paths

 一刷 07/2022

Version #1 DP

写了一个bug就是MOD应该是(int)(1e9+7)而不是(int)(10e9 + 7)

其他的没有什么特别的

跟以前做的一个计算落在board里面的概率的题几乎一模一样

Time O(KMN) - K max steps, MN area of the board

Space O(MN)

Runtime: 12 ms, faster than 43.75% of Java online submissions for Out of Boundary Paths.

Memory Usage: 41.4 MB, less than 92.29% of Java online submissions for Out of Boundary Paths.

class Solution {

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    private int MOD = (int)(1e9 + 7);

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {

        int result = 0;

        int[][] prevCount = new int[m][n];

        prevCount[startRow][startColumn] = 1;

        while (maxMove-- > 0) {

            int[][] currCount = new int[m][n];

            for (int y = 0; y < m; y++) {

                for (int x = 0; x < n; x++) {

                    for (int i = 0; i < 4; i++) {

                        int ny = y + dy[i];

                        int nx = x + dx[i];

                        if (ny < 0 || nx < 0 || ny >= m || nx >= n) {

                            result = (result + prevCount[y][x]) % MOD;

                        } else {

                            currCount[ny][nx] = (currCount[ny][nx] + prevCount[y][x]) % MOD;

                        }

                    }

                }

            }

            prevCount = currCount;

        }

        return result;

    }

}