基本优化方法
可行性剪枝
所谓可行性剪枝，顾名思义，就是当当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。
排除等效冗余
所谓排除等效冗余，就是当几个枝桠具有完全相同的效果的时候，只选择其中一个走就可以了。
最优性剪枝
所谓最优性剪枝，是在我们用搜索方法解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候，已经比已经搜到的最优解要不优了，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。
顺序剪枝
普遍来讲，搜索的顺序是不固定的，对一个问题来讲，算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。
记忆化
记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：
就是记录搜索的每一个状态，当重复搜索到相同的状态的时候直接返回。
何时用dfs，何时用动态规划
- 首先看取值范围，递归回溯一维数组，100就是深度的极限了（但是只要会剪枝和记忆化也是可以的）
- 如果是求走迷宫的【路径】，必然是回溯；如果是走迷宫的【路径的条数】，必然是dp——–(这个竟然屡试不爽！！！！)
栗子
576. 出界的路径数
给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。
给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。
第一个版本的垃圾代码
class Solution {
// 1表示出轨，0表示没出轨
int[][] mat;
int ret;
int max;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
ret = 0;
max = maxMove;
mat = new int[m + 2][n + 2];
for(int i = 1; i < m + 1; i++){
mat[i][0] = 1;
mat[i][n + 1] = 1;
}
for(int i = 1; i < n + 1; i++){
mat[0][i] = 1;
mat[m + 1][i] = 1;
}
dfs(startRow + 1,startColumn + 1,0);
return ret;
}
private void dfs(int row,int col,int step){
if(row < 0 || row >= mat.length || col < 0 || col >= mat[0].length || step > max)return;
if(mat[row][col] == 1){
ret++;
return;
}
dfs(row - 1,col,step + 1);
dfs(row + 1,col,step + 1);
dfs(row,col - 1, step + 1);
dfs(row, col + 1,step + 1);
}
}
//超时因为dfs函数返回值为空，导致很难使用cache记忆化，以前写dfs留下了的坏习惯，不喜欢dfs有返回值觉得麻烦。
第二个版本
class Solution {
// 1表示出轨，0表示没出轨
int[][] mat;
// 四个方向
int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int max;
// 取余
int mod = (int)1e9 + 7;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
max = maxMove;
mat = new int[m + 2][n + 2];
for(int i = 1; i < m + 1; i++){
mat[i][0] = 1;
mat[i][n + 1] = 1;
}
for(int i = 1; i < n + 1; i++){
mat[0][i] = 1;
mat[m + 1][i] = 1;
}
return dfs(startRow + 1,startColumn + 1,0);
}
private int dfs(int row,int col,int step){
if(row < 0 || row >= mat.length || col < 0 || col >= mat[0].length || step > max)return 0;
if(mat[row][col] == 1){
return 1;
}
int ret = 0;
for(int[] d : dir){
ret += dfs(row + d[0],col + d[1],step + 1) % mod;
}
return ret;
}
}
//超时优化了dfs递归的写法
剪枝优化版本
就是可行性剪枝，剪枝技巧就是每次DFS的时候判断如果小球不管怎么移动都无法超出网格，那从这个点开始往后的枝就都可以剪掉了，简单修改下代码即可：
class Solution {
int[][] mat;
int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int max;
int mod = (int)1e9 + 7;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
max = maxMove;
mat = new int[m + 2][n + 2];
for(int i = 1; i < m + 1; i++){
mat[i][0] = 1;
mat[i][n + 1] = 1;
}
for(int i = 1; i < n + 1; i++){
mat[0][i] = 1;
mat[m + 1][i] = 1;
}
return dfs(startRow + 1,startColumn + 1,0);
}
private int dfs(int row,int col,int step){
if(row < 0 || row >= mat.length || col < 0 || col >= mat[0].length || step > max)return 0;
if(mat[row][col] == 1)return 1;
int last = max - step;//剩余的步数
// 剪枝：如果小球不管怎么移动都无法越出网格，那就剪掉这个枝
if(row - last >= 1 && row + last < mat.length - 1 && col - last >= 1 && col + last < mat[0].length - 1)return 0;
int ret = 0;
for(int[] d : dir){
ret += dfs(row + d[0],col + d[1],step + 1) % mod;
ret %= mod;
}
return ret;
}
}
// 剪枝了依然超时记忆化搜索
增加一个缓存，记录下来从每个位置在给定移动次数的范围内可以越界的次数。
class Solution {
// 1表示出轨，0表示没出轨
int[][] mat;
// 缓存
int[][][] cache;
// 4个方向
int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int max;
int mod = (int)1e9 + 7;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
max = maxMove;
mat = new int[m + 2][n + 2];
for(int i = 1; i < m + 1; i++){
mat[i][0] = 1;
mat[i][n + 1] = 1;
}
for(int i = 1; i < n + 1; i++){
mat[0][i] = 1;
mat[m + 1][i] = 1;
}
cache = new int[m + 1][n + 1][maxMove + 1];
for(int i = 1; i < m + 1; i++){
for(int j = 1; j < n + 1; j++){
for(int k = 0; k < maxMove + 1; k++)cache[i][j][k] = -1;
}
}
return dfs(startRow + 1,startColumn + 1,0);
}
private int dfs(int row,int col,int step){
if(row < 0 || row >= mat.length || col < 0 || col >= mat[0].length || step > max)return 0;
if(mat[row][col] == 1){
return 1;
}
// 缓存中存在
if(cache[row][col][step] != -1)return cache[row][col][step];
int last = max - step;
// 剪枝：如果小球不管怎么移动都无法越出网格，那就剪掉这个枝
if(row - last >= 1 && row + last < mat.length - 1 && col - last >= 1 && col + last < mat[0].length - 1)return 0;
int ret = 0;
for(int[] d : dir){
ret += dfs(row + d[0],col + d[1],step + 1) % mod;
ret %= mod;
}
// 记录缓存
cache[row][col][step] = ret;
return ret;
}
}
// ak动态规划
一般来说，能使用记忆化搜索的题目都可以使用动态规划来解：
dp[i][j][k]表示从 [i,j] 位置最多移动 k 次能够把小球移出去的最大路径数量
dp[i][j][k] = dp[i-1][j][k-1] + dp[i+1][j][k-1] + dp[i][j-1][k-1] + dp[i][j+1][k-1]
注意边界条件，如果是正方形的四个顶点，有两种方法越界，其他边上的位置只有一种方法越界。
另外，要注意移动次数2的都是从移动次数为1的扩展来的，同理，移动次数3的都是从移动次数为2的扩展来的，所以要注意循环的顺序。
class Solution {
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
int[][][] dp = new int[m][n][maxMove + 1];
int[][] direct = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
int mod = (int)1e9 + 7;
// 移动步数2的都是从移动步数1的转移来的
// 移动步数3的都是从移动步数2的转移来的
// 所以，要从移动步数从1开始递增
for(int k = 1; k <= maxMove; k++){
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
// 初始化，处理四条边
if(i == 0)dp[i][j][k]++;
if(i == m - 1)dp[i][j][k]++;
if(j == 0)dp[i][j][k]++;
if(j == n - 1)dp[i][j][k]++;
// 中间的位置，向四个方向延伸
for(int[] d : direct){
int x = i + d[0],y = j + d[1];
if(x >= 0 && x < m && y >= 0 && y < n){
dp[i][j][k] = (dp[i][j][k] + dp[x][y][k - 1]) % mod;
}
}
}
}
}
return dp[startRow][startColumn][maxMove];
}
}但是，仍然没办法跟记忆化搜索相比，因为记忆化搜索我们可以通过剪枝等手段减少循环（递归）的次数，但是动态规划的方法每一轮都要把（m∗n）个格子重新计算一遍。
526. 优美的排列
假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：
- 第 i 位的数字能被 i 整除
- i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？
暴力版本
class Solution {
boolean[] used;
public int countArrangement(int n) {
used = new boolean[n + 1];
return dfs(n,1);
}
private int dfs(int n , int idx){
if(idx == n + 1)return 1;
int ans = 0;
for(int i = 1; i <= n; i++){
if(!used[i]){
if(i % idx == 0 || idx % i == 0){
used[i] = true;
ans += dfs(n,idx + 1);
used[i] = false;
}
}
}
return ans;
}
}状态压缩
我们仔细看题目给的限制条件是：n不会超过15，所以，我们可以只使用一个 int 类型的变量代替used数组，这其实就是状态压缩了。
class Solution {
public int countArrangement(int n) {
return dfs(n,1,0);
}
private int dfs(int n , int idx,int used){
if(idx == n + 1)return 1;
int ans = 0;
for(int i = 1; i <= n; i++){
if(((1 << i) & used) == 0){
if(i % idx == 0 || idx % i == 0){
ans += dfs(n,idx + 1,(1 << i) | used);
}
}
}
return ans;
}
}记忆化搜索
有了状态压缩基础就可以把used数组当成一个状态，idx当成一个状态缓存起来避免重复计算
class Solution {
int[][] cache;
public int countArrangement(int n) {
cache = new int[n + 1][1 << n + 1];
for(int i = 0; i < n + 1; i++)Arrays.fill(cache[i],-1);
return dfs(n,1,0);
}
private int dfs(int n , int idx,int used){
if(idx == n + 1)return 1;
if(cache[idx][used] != -1)return cache[idx][used];
int ans = 0;
for(int i = 1; i <= n; i++){
if(((1 << i) & used) == 0){
if(i % idx == 0 || idx % i == 0){
ans += dfs(n,idx + 1,(1 << i) | used);
}
}
}
cache[idx][used] = ans;
return ans;
}
}动态规划
定义 dp[i][used] 为考虑前 i 个数，且当前选择方案为 used 的所有方案数量
一个显然的初始化条件为dp[0][0] = 1，代表当我们不考虑任何数（i=0）的情况下，一个数都不被选择（used = 0）为一种合法方案。
根据状态定义，位置 i 选了数值 num，通过位运算我们可以直接得出决策位置 i 之前的状态是什么：used&(¬(1<<(num−1)))，代表将 used 的二进制表示中的第 num 位置为 0。
一些细节：由于给定的数值范围为 [1,n]，但实现上为了方便，我们使用 used 从右往左的第 0 位表示数值 1 选择情况，第 1 位表示数值 2 的选择情况 … 即对选择数值 num 做一个 −1 的偏移。
class Solution {
public int countArrangement(int n) {
int mask = 1 << n;
int[][] dp = new int[n + 1][mask];
dp[0][0] = 1;
for(int i = 1; i <= n; i++){
// 枚举所有的状态
for(int used = 0; used < mask; used++){
// 枚举位置 i（最后一位）选的数值是 num
for(int num = 1; num <= n; num++){
// 首先 num 在 used 中必须是 1
if(((used >> (num - 1)) & 1) == 1){
// 数值 num 和位置 i 之间满足任一整除关系
if(i % num == 0 || num % i == 0){
// used & (~(1 << (num - 1))) 代表将 used 中数值 num 的位置置零
dp[i][used] += dp[i - 1][used & (~(1 << (num - 1)))];
}
}
}
}
}
return dp[n][mask - 1];
}
}63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
有了上边两题的基础这题迎刃而解~
class Solution {
int[][] mat;
int m,n;
int[][] dist = new int[][]{{1,0},{0,1}};
//不记忆化的话会超时，毕竟100²的范围
int[][] cache;
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
mat = obstacleGrid;
m = mat.length;
n = mat[0].length;
cache = new int[m][n];
for(int i = 0; i < m; i++)Arrays.fill(cache[i],-1);
return dfs(0,0);
}
private int dfs(int x,int y){
if(x < 0 || x >= m || y < 0 || y >= n || mat[x][y] == 1)return 0;
if(x == m - 1 && y == n - 1){
return 1;
}
if(cache[x][y] != -1)return cache[x][y];
int ans = 0;
for(int[] d : dist){
ans += dfs(x + d[0],y + d[1]);
}
cache[x][y] = ans;
return ans;
}
}动态规划
根据上边的dfs很自然的得到递推公式：dp[i][j] = dp[i][j - 1] + dp[x - 1][j]
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if(obstacleGrid[0][0] == 1)return 0;
// 初始化
dp[0][0] = 1;
for(int i = 1; i < m; i++){
if(obstacleGrid[i][0] != 1)dp[i][0] = 1;
else break;
}
for(int i = 1; i < n; i++){
if(obstacleGrid[0][i] != 1)dp[0][i] = 1;
else break;
}
// 遍历
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 0){
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
}
return dp[m - 1][n - 1];
}
}
