|
29 | 29 |
|
30 | 30 | */ |
31 | 31 | public class _576 { |
32 | | - |
33 | | - /**reference: https://leetcode.com/articles/out-of-boundary-paths/#approach-2-recursion-with-memoization-accepted*/ |
34 | | - public int findPaths(int m, int n, int N, int x, int y) { |
35 | | - int M = 1000000000 + 7; |
36 | | - int[][] dp = new int[m][n]; |
37 | | - dp[x][y] = 1; |
38 | | - int count = 0; |
39 | | - for (int moves = 1; moves <= N; moves++) { |
40 | | - int[][] temp = new int[m][n]; |
41 | | - for (int i = 0; i < m; i<
8000
/span>++) { |
42 | | - for (int j = 0; j < n; j++) { |
43 | | - if (i == m - 1) { |
44 | | - count = (count + dp[i][j]) % M; |
45 | | - } |
46 | | - if (j == n - 1) { |
47 | | - count = (count + dp[i][j]) % M; |
48 | | - } |
49 | | - if (i == 0) { |
50 | | - count = (count + dp[i][j]) % M; |
51 | | - } |
52 | | - if (j == 0) { |
53 | | - count = (count + dp[i][j]) % M; |
| 32 | + public static class Solution1 { |
| 33 | + /** |
| 34 | + * reference: https://leetcode.com/articles/out-of-boundary-paths/#approach-2-recursion-with-memoization-accepted |
| 35 | + */ |
| 36 | + public int findPaths(int m, int n, int N, int x, int y) { |
| 37 | + int M = 1000000000 + 7; |
| 38 | + int[][] dp = new int[m][n]; |
| 39 | + dp[x][y] = 1; |
| 40 | + int count = 0; |
| 41 | + for (int moves = 1; moves <= N; moves++) { |
| 42 | + int[][] temp = new int[m][n]; |
| 43 | + for (int i = 0; i < m; i++) { |
| 44 | + for (int j = 0; j < n; j++) { |
| 45 | + if (i == m - 1) { |
| 46 | + count = (count + dp[i][j]) % M; |
| 47 | + } |
| 48 | + if (j == n - 1) { |
| 49 | + count = (count + dp[i][j]) % M; |
| 50 | + } |
| 51 | + if (i == 0) { |
| 52 | + count = (count + dp[i][j]) % M; |
| 53 | + } |
| 54 | + if (j == 0) { |
| 55 | + count = (count + dp[i][j]) % M; |
| 56 | + } |
| 57 | + temp[i][j] = (((i > 0 ? dp[i - 1][j] : 0) + (i < m - 1 ? dp[i + 1][j] : 0)) % M |
| 58 | + + ((j > 0 ? dp[i][j - 1] : 0) + (j < n - 1 ? dp[i][j + 1] : 0)) % M) % M; |
54 | 59 | } |
55 | | - temp[i][j] = (((i > 0 ? dp[i - 1][j] : 0) + (i < m - 1 ? dp[i + 1][j] : 0)) % M |
56 | | - + ((j > 0 ? dp[i][j - 1] : 0) + (j < n - 1 ? dp[i][j + 1] : 0)) % M) % M; |
57 | 60 | } |
| 61 | + dp = temp; |
58 | 62 | } |
59 | | - dp = temp; |
| 63 | + return count; |
60 | 64 | } |
61 | | - return count; |
62 | 65 | } |
63 | 66 |
|
64 | 67 | } |
0 commit comments