【LeetCode】576. 出界的路径数

路径数"/>

【LeetCode】576. 出界的路径数

题目

LeetCode自搜

题解

建议看《忆甜思苦，DFS + 记忆化搜索》，链接：
/
我是看了官方题解自闭后，发现的这个宝藏题解，
如果直接看觉得过于简洁的话，可以先看一遍更详细的官方题解。

代码

class Solution {private static final int[][] DIR = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private static final int MOD = (int)(1e9+7);private Map<Integer, Integer> map = new HashMap<>();public int findPaths(int m, int n, int moves, int r, int c) {//情况一：出界，+1if (r < 0 || r >= m || c < 0 || c >= n) {return 1;}//情况二：moves步数用完if (moves == 0) return 0;//情况三：已求，直接取int key = r*2500+c*50+moves;if (map.containsKey(key)) {return map.get(key);}//Startint rst = 0;for(int[] d : DIR) {rst = (rst + findPaths(m, n, moves-1, r+d[0], c+d[1]))%MOD;}map.put(key, rst);return rst;}
}

心得

1.

private static final

static：经常调用时使用
final：常量不变时使用

 
2.

private Map<Integer, Integer> map = new HashMap<>();if (map.containsKey(key)) {return map.get(key);}map.put(key, rst);

Map映射的 定义、取值、添加

 
3.

int key = r*2500+c*50+moves;

二位数组一维化（题目里为mod50的三维矩阵，这里以mod4的二维矩阵举例如图）

 
4.

private static final int[][] DIR = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; 

移动方向表示

 
5.

5.for(int[] d : DIR) 

特别的for循环