回溯法

原理

当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”

方法模板

private void backtrack("原始参数") { 
  //终止条件(递归必须要有终止条件) 
  if ("终止条件") { 
    //一些逻辑操作（可有可无，视情况而定） 
    return; 
  } 
  横向处理
  for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) { 
    //一些逻辑操作（可有可无，视情况而定） 
    //做出选择 
    //递归 
    纵向处理
    backtrack("新的参数"); 
    //一些逻辑操作（可有可无，视情况而定） 
    //撤销选择 
  } 
}

本题

1. 数据可以从任意位置进入，去找寻最长路径
2. 判断边界（终止）条件

if(i < 0 || i >= n || j < 0 || j >= m){
     return pathLength-1;
}

3. 进入条件

• 大于当前值；
  分上下左右四个情况，分别判断
• 不能重复；

int curVal = matrix[i][j]; //记录当前值，便于回溯
matrix[i][j] = -1;
//递归完成后再回溯回去
matrix[i][j] = curVal;