1. 顺序尝试
顺序尝试包括：
- 从左到右的尝试
- 从上到下的尝试
- 有规律的尝试
1.1 从左到右的尝试
1.1.1 机器人走路问题
题目：给你标号为 1、2、3、……、N 的 N 个位置，机器人初始停在 S 位置上，走 K 步后停在 E 位置上的走法有多少种。
注：机器人在 1 位置上时只能向右走，在 N 位置上时只能向左走，其它位置既可向右又可向左。
递归过程：
/**
* 固定参数：
* 1. N个格子
* 2. 最终的目标为E
* 可变参数：
* 1. 还剩余的步数 rest
* 2. 当前位置 cur
*
* 方法含义：
* 在N个格子上，当剩余rest步走完时，从cur到目标E位置的，走法
* or
* 在N个格子上，从cur出发，当剩余rest步走完时，刚的走到E的，走法
*
* @return 返回有多少种走法
*/
public int process(int N, int E, int rest, int cur){
//base case
//如果还剩0步，判断当前位置是否是结束点，如果是，返回走法1；如果不是，返回0代表该走法不行。
if(rest == 0){
return cur == E ? 1 : 0;
}
//边界问题
if(cur == 1){
//只能往右走
return process(N, E, rest-1, cur + 1);
}
if(cur == N){
//只能往左走
return process(N, E, rest-1, cur - 1);
}
//依赖关系
return process(N, E, rest-1, cur-1) + process(N, E, rest-1, cur + 1);
}
动态规划过程：
public int processDp(int N, int E, int K, int S){
//1. 问题定义
//dp[rest][cur] 代表在cur位置上，走完剩余rest步到达E位置的【走法】
//rest的范围为0~K,申请K+1，cur的范围1-N, 申请N+1
int dp[][] = new int[K+1][N+1];
//2. 边界问题
for (int rest = 0; rest <= K; rest++) {
for (int cur = 0; cur <= N; cur++) {
if(rest == 0 && cur == E){
//对应递归bad case，当rest=0且cur=E时返回走法1，其他全部为0
dp[rest][cur] = 1;
}
}
}
//3. 状态方程
for (int rest = 1; rest <= K; rest++) {
for (int cur = 1; cur <= N; cur++){
if(cur == 1){
dp[rest][cur] = dp[rest-1][cur+1];
}else if(cur == N){
dp[rest][cur] = dp[rest-1][cur-1];
}else{
dp[rest][cur] = dp[rest-1][cur-1] + dp[rest-1][cur+1];
}
}
}
//4. 返回结果
//返回还有k步要走，从S位置出发的，到达E的走法
return dp[K][S];
}
1.2 从上到下的尝试
1.2.1 马走棋盘问题
递归过程：
/**
* 固定参数：
* 棋盘的最大x：mx
* 棋盘的最大y: my
*
* 结束的位置 ex, ey
*
* 可变参数：
* 剩余可走的步数：rest
* 当前的位置：cx, cy
*
* 方法含义：
* 当剩余步数为rest步时，从当前位置为(cx,cy)出发，到达终点（ex,ey）的走法
* or
* 从当前位置为(cx,cy)出发，走完剩余的rest步时，刚好到达（ex,ey）的走法
*
* @return 返回一共多少种走法
*/
public int process(int mx, int my, int ex, int ey, int rest, int cx, int cy){
//base case
//当剩余的步数为0时，代表已经不能走了，如果当前的位置和终点的位置相同，那么走法为1，否则为0
if(rest == 0){
return (cx == ex && cy == ey) ? 1 : 0;
}
//边界问题
//如果走了一步后，当前位置已经跑出了棋盘外，那么该走法直接为0
if(cx <= 0 || cx > mx || cy<= 0 || cy > my){
return 0;
}
//依赖关系：从当前位置可以走到的8个位置
//从(cx-2, cy-1) 出发，走完剩余的rest-1步，刚好到达(ex,ey)的走法
int way1 = process(mx, my, ex, ey, rest-1, cx-2, cy-1);
//同理
int way2 = process(mx, my, ex, ey, rest-1, cx-2, cy+1);
int way3 = process(mx, my, ex, ey, rest - 1, cx + 2, cy - 1);
int way4 = process(mx, my, ex, ey, rest - 1, cx + 2, cy + 1);
int way5 = process(mx, my, ex, ey, rest - 1, cx - 1, cy - 2);
int way6 = process(mx, my, ex, ey, rest - 1, cx - 1, cy + 2);
int way7 = process(mx, my, ex, ey, rest - 1, cx + 1, cy - 2);
int way8 = process(mx, my, ex, ey, rest - 1, cx + 1, cy + 2);
//返回结果
return way1 + way2 + way3 + way4 + way5 + way6 +way7 + way8;
}
动态规划过程：
public int processDp(int mx, int my, int ex, int ey, int K, int sx, int sy){
//1. 问题定义
//dp[rest][cx][cy] 代表在(cx,cy)位置上，走完剩余rest步到达(ex,ey)位置的【走法】
//rest的范围为0~K,申请K+1，cx的范围时1~mx,cy的范围为1～my,所以申请mx+1,my+1大小即可
int dp[][][] = new int[K+1][mx+1][my+1];
//2. 边界问题
for (int rest = 0; rest <= K; rest++) {
for (int cx = 0; cx <= mx; cx++) {
for (int cy = 0; cy <= my; cy++) {
if(rest == 0 && cx == ex && cy == ey){
//对应递归bad case，当rest=0且cx == ex && cy == ey时返回走法1，其他全部为0
dp[rest][cx][cy] = 1;
}
}
}
}
//3. 状态方程
for (int rest = 1; rest <= K; rest++) {
for (int cx = 1; cx <= mx; cx++) {
for (int cy = 1; cy <= my; cy++) {
if(cx <= 0 || cx > mx || cy<= 0 || cy > my){
dp[rest][cx][cy] = 0;
}else{
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx-2, cy-1);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx-2,cy+1);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx+2,cy-1);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx+2,cy+1);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx-1, cy-2);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx-1,cy+2);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx+1, cy-2);
dp[rest][cx][cy] += getValue(mx, my, dp,rest-1,cx+1,cy+2);
}
}
}
}
//4. 返回结果
//返回还有k步要走，从(sx,sy)位置出发的，到达E的走法
return dp[K][sx][sy];
}
private int getValue(int mx, int my, int[][][] dp, int rest, int cx, int cy){
if(cx <= 0 || cx > mx || cy<= 0 || cy > my){
return 0;
}
return dp[rest][cx][cy];
}
总结：整个过程可以想象为一个立体，z走为步数，从0到K步，平面为位置x，y，过程就是从下到上根据依赖关系不断填表的过程。
1.3 有规律的尝试
2. 范围上的尝试
原则：
- 一定要重点讨论开头和结尾的可能性，以开头和结尾来划分和讨论
- 以i开头，不以j结尾的情况
- 以i开头，以j结尾的情况
- 不以i开头，以j结尾的情况
- 不以i开头，不以j结尾的情况
- 如果以开头和结尾的情况分析不行，那范围尝试用不了
- 范围尝试重要的原则是：在可能性的分类下，把这个域的问题解决掉
- 回溯决策
技巧：
- 符合范围上尝试的模型，那么dp表是2维的，那么表的下半部分一般没用（不符合题意）
- 递归在设计的时候一定要遵守：无后效性递归，即所有决策都体现在小问题的参数上
2.1 最长回文子序列
题目：
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
递归过程：
/**
* 固定参数：s
*
* 可变参数：从i开头，到j结尾
*
* 方法的含义:
* 从i到j位置的最长回文子序列
*
* @return 最长回文子序列的长度
*/
private int process(String s, int i, int j){
//base case
//如果i=j代表1个字符，看是否相等，如果相等回文子序列，返回最长长度为1
if(i == j){
return s.charAt(i) == s.charAt(j)?1:0;
}
//如果i+1=j代表2个字符，看是否相等，如果相等回文子序列，返回最长长度为2, 不等为1
if(i + 1 == j){
return s.charAt(i) == s.charAt(j)?2:1;
}
//边界关系，对角线下半边都是0
if(i > j || i>= s.length() || j>=s.length()){
return 0;
}
//依赖关系，范围上分析可能性
//p1: 不以i开头，以j结尾的最长回文子序列 就是 i～j上的最长回文子序列
int p1 = process(s, i+1, j);
//p2: 以i开头，不以j结尾的最长回文子序列 就是 i～j上的最长回文子序列
int p2 = process(s, i, j - 1);
int p34 = 0;
//p3: 以i开头，以j结尾的最长回文子序列 就是 i～j上的最长回文子序列
if(s.charAt(i) == s.charAt(j)){
//+2代表i和j位置的字符也要加进去
p34 = process(s, i + 1, j - 1) + 2;
}else{
//p4: 不以i开头，不以j结尾的最长回文子序列 就是 i～j上的最长回文子序列
p34 = process(s, i + 1, j - 1);
}
//返回结果
return Math.max(Math.max(p1,p2), p34);
}
动态规划过程：
private int processDp(String s){
//1.问题定义
//dp[i][j] 代表从i到j位置上的最长回文子序列的长度
//i的范围是0~s.length-1,大小为s.length，同理j一样
int[][] dp = new int[s.length()][s.length()];
//2.边界问题
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < s.length(); j++) {
//base case
//如果i=j代表1个字符，看是否相等，如果相等回文子序列，返回最长长度为1
if(i == j){
dp[i][j] = s.charAt(i) == s.charAt(j)?1:0;
}
//如果i+1=j代表2个字符，看是否相等，如果相等回文子序列，返回最长长度为2, 不等为1
if(i + 1 == j){
dp[i][j] = s.charAt(i) == s.charAt(j)?2:1;
}
//对角线下半边都是0
if(i>j){
dp[i][j] = 0;
}
}
}
//3.状态方程，填表的顺序很重要，从下到上，从左到右
for (int i = s.length()-1; i >= 0; i--) {
//对角线的2行已经填过了，所以是i+2
for (int j = i+2; j <= s.length()-1; j++ ) {
//p1 process(s, i+1, j);
int p1 = dp[i+1][j];
//p2 process(s, i, j - 1);
int p2 = dp[i][j-1];
//p34
int p34;
if(s.charAt(i) == s.charAt(j)){
//p3 process(s, i + 1, j - 1) + 2;
p34 = dp[i+1][j-1] +2;
}else {
//p4 process(s, i + 1, j - 1);
p34 = dp[i+1][j-1];
}
dp[i][j] = Math.max(Math.max(p1,p2), p34);
}
}
//4.返回结果
return dp[0][s.length()-1];
}
2.2 让字符串成为回文串的最少
题目：
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。请你返回让 s 成为回文串的 最少操作次数 。
范围尝试的思路：
- 可能性p1: 以i开头，以j结尾 的最小插入次数就是使i-j范围成为回文字符串的最小次数
- 如果i和j位置的字符串相同，那么dp[i][j] = dp[i+1][j-1]
- 如果i和j位置的字符串不相同，那么dp[i][j] = dp[i+1][j-1]+2 (由于是求最小，对比线)
- 可能性p2：以i开头，不以j结尾的 最小插入次数就是使i-j范围成为回文字符串的最小次数，此时就必须在[i-1]的位置插入一个和j位置相同的字符，才能使字符串为回文串，所以：dp[i][j] = dp[i][j-1] + 1
- 可能性p3：不以i开头，以j结尾的 最小插入次数就是使i-j范围成为回文字符串的最小次数，同上，dp[i][j] = dp[i+1][j] + 1
动态规划：
public int processDp(String s){
//1.问题定义
//dp[i][i] 代表从i到j位置，让字符成为回文串的至少添加次数
//i范围0～s.length-1, 大小s.length，j同理
int[][]dp = new int[s.length()][s.length()];
//2.边界问题
for (int i = 0; i <s.length() ; i++) {
for (int j = 0; j < s.length(); j++) {
if(i==j){
dp[i][j] = 0;
}
if(i+1 == j){
dp[i][j] = s.charAt(i) == s.charAt(j) ? 0 : 1;
}
}
}
//3.状态方程
//依赖关系，从下到上，从左到右
for (int i = s.length()-1; i >= 0 ; i--) {
for (int j = i+2; j <= s.length()-1; j++) {
int ans = Integer.MAX_VALUE;
if(s.charAt(i) == s.charAt(j)){
int p1 = dp[i+1][j-1];
ans = Math.min(ans, p1);
}else{
int p2 = dp[i][j-1] +1;
int p3 = dp[i+1][j] + 1;
ans = Math.min(Math.min(ans, p2),p3);
}
dp[i][j] = ans;
}
}
//4.返回结果
return dp[0][s.length()-1];
}
2.3 运算符表达式desired
题目：给定一个只有0（假）、1（真）、&（逻辑与）、｜（逻辑或）和 ^（异或）的五种字符串组成的express表达式，再给定一个布尔类型值desired，返回express能有多少种组合，可以达到desired的效果。
eg: express = "1^0|0|1", desired=false，那么有以下几种可能：
- 1^((0|0)|1)
- 1^((0|(0|1))
的组合可以返回false，所以组合数为2。
注：无组合数返回0
递归：
public int getNums(String str, boolean desired){
if(str == null || str.length() ==0){
return 0;
}
if(!isValid(str)){
return 0;
}
return process(str.toCharArray(), desired, 0, str.length()-1);
}
/**
* 固定参数:
* express 表达式数组
* desired 要的布尔结果
*
* 可变参数：
* L:数组中的开始位置
* R:数组中的结束位置
*
* 方法含义：
* 从express[i...j]位置上有多少中组合方式，能让结果=desired
* or
* 从express[i...j]位置上组合出结果为desired的方法有多少种
*
* 无后效性要求：i j 不要压中逻辑运算符
*
* @return 组合方式方法数
*/
public int process(char[] express,boolean desired, int i, int j){
//bad case
if(i == j){
//最后的位置，如果为1，那么desire=true时，组合数为1，否则整个组合数为0
if(express[i] == '1'){
return desired ? 1 : 0;
}else {
//如果为0，那么desire=false时，组合数为1，否则整个组合数为0
return desired ? 0 : 1;
}
}
int res = 0;
//依赖关系，分析可能性
//p1: 不以i开头，以j结尾，[i,i][符号][i+2, j] 的组合数，由于组合数可以任意位置结合，那么可能性有 j-i+1个
//中间有px : [i,i+2][符号][i+4, j] 的组合数 ～ [i,j-4][符号][j-2, j] 种可能性，
//pn: 以i开头，不以j结尾就是 [i,j-2][符号][j, j] 的组合数
if(desired){//题目要求为true
//从x开始尝试i-j上的每个逻辑符号, x为符号位
for (int x = i+1 ; x < j; x+=2) {
switch (express[x]) {
case '&':
//如果是&的符号：[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, true, i, x - 1) * process(express, true, x + 1, j);
break;
case '|':
//如果是|的符号：[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, true, i, x - 1) * process(express, true, x + 1, j);
//[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为false的数量
res += process(express, true, i, x - 1) * process(express, false, x + 1, j);
//[i,x-1]位置上组合出为false的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, false, i, x - 1) * process(express, true, x + 1, j);
break;
case '^':
//如果是|的符号：[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为false的数量
res += process(express, true, i, x - 1) * process(express, false, x + 1, j);
//[i,x-1]位置上组合出为false的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, false, i, x - 1) * process(express, true, x + 1, j);
break;
}
}
}else{//题目要求为false
//从x开始尝试i-j上的每个逻辑符号, x为符号位
for (int x = i+1 ; x < j; x+=2) {
switch (express[x]) {
case '&':
//如果是|的符号：[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, true, i, x - 1) * process(express, true, x + 1, j);
//[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为false的数量
res += process(express, true, i, x - 1) * process(express, false, x + 1, j);
//[i,x-1]位置上组合出为false的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, false, i, x - 1) * process(express, true, x + 1, j);
break;
case '|':
//如果是&的符号：[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, true, i, x - 1) * process(express, true, x + 1, j);
break;
case '^':
//如果是|的符号：[i,x-1]位置上组合出为true的数量 * [x+1,j]位置上组合出为true的数量
res += process(express, true, i, x - 1) * process(express, true, x + 1, j);
//[i,x-1]位置上组合出为false的数量 * [x+1,j]位置上组合出为false的数量
res += process(express, false, i, x - 1) * process(express, false, x + 1, j);
break;
}
}
}
//返回结果, 所有可能性的组合数加起来就是结果
return res;
}
动态规划：
public int processDp(String expressStr, boolean desired){
int length = expressStr.length();
char[] express = expressStr.toCharArray();
//1.问题定义
//dpTrue[i][j]代表express中从i-j位置上可以组合出来true的组合数
//dpFalse[i][j]代表express中从i-j位置上可以组合出来false的组合数
//i:0~express.length-1,大小为express，同理j也是
int dpTrue[][] = new int[length][length];
int dpFalse[][] = new int[length][length];
//2.边界问题，i和j都是符号位置不填,数字位填. 且对角线左半下区不需要填
for (int i = 0; i < length; i+=2) {
dpTrue[i][i] = express[i] == '1' ? 1 : 0;
dpFalse[i][i] = express[i] == '0' ? 1 : 0;
}
//3.状态方程, 遍历顺序：从下到上，从左到右
for (int i = length-3 ; i>=0; i-=2) {
for (int j = i + 2 ; j< length; j+=2) {
//从x开始尝试i-j上的每个逻辑符号, x为符号位。枚举过程
for (int x = i+1 ; x < j; x+=2) {
switch (express[x]) {
case '&':
dpTrue[i][j] += dpTrue[i][x-1] * dpTrue[x+1][j];
break;
case '|':
dpTrue[i][j] += dpTrue[i][x-1] * dpTrue[x+1][j];
dpTrue[i][j] += dpTrue[i][x-1] * dpFalse[x+1][j];
dpTrue[i][j] += dpFalse[i][x-1] * dpTrue[x+1][j];
break;
case '^':
dpTrue[i][j] += dpTrue[i][x-1] * dpTrue[x+1][j];
dpTrue[i][j] += dpFalse[i][x-1] * dpFalse[x+1][j];
break;
}
switch (express[x]){
case '&':
dpFalse[i][j] += dpTrue[i][x-1] * dpFalse[x+1][j];
dpFalse[i][j] += dpFalse[i][x-1] * dpTrue[x+1][j];
dpFalse[i][j] += dpFalse[i][x-1] * dpFalse[x+1][j];
break;
case '|':
dpFalse[i][j] += dpFalse[i][x-1] * dpFalse[x+1][j];
break;
case '^':
dpFalse[i][j] += dpTrue[i][x-1] * dpFalse[x+1][j];
dpFalse[i][j] += dpFalse[i][x-1] * dpTrue[x+1][j];
break;
}
}
}
}
//4.返回结果, 根据题目要求的结果，从对应的表中找到[0...length-1]的值
return desired ? dpTrue[0][length-1] : dpFalse[0][length-1];
}
