一 最长回文子串
1.1 描述
给定一个字符串str，返回这个字符串的最长回文子序列长度
比如 ： str = “a12b3c43def2ghi1kpm”
最长回文子序列是“1234321”或者“123c321”，返回长度7
1.2 分析
1.2.1 先将原传逆序，求原串和反转后的串的最长公共子序列就是原串的最长回文子序列
1.2 分析
1.2.1 先将原传逆序，求原串和反转后的串的最长公共子序列就是原串的最长回文子序列
1.3 反转求最长公共子序列 代码
public static int longestPalindromeSubseq1(String s) {
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
char[] str = s.toCharArray();
char[] reverse = reverse(str);
return longestCommonSubsequence(str, reverse);
}
public static int longestCommonSubsequence(char[] str1, char[] str2) {
int N = str1.length;
int M = str2.length;
int[][] dp = new int[N][M];
dp[0][0] = str1[0] == str2[0] ? 1 : 0;
for (int i = 1; i < N; i++) {
dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
}
for (int j = 1; j < M; j++) {
dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
if (str1[i] == str2[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
}
}
}
return dp[N - 1][M - 1];
}1.3.1 分析二 上节用的是样本对应模型，这里用别的做法 （范围尝试模型 这种模型特别在乎讨论开头如何如何 结尾如何如何）
样本对应模型（特别在乎两个样本结尾如何如何） 范围尝试模型往开头如何如何，结尾如何如何
范围讨论如下-递归含义的定义如下
1.3.2 分析 有以下四种情况
1）不以L开头，不以R结尾
2）以L开头，不以R结尾
3）不以L开头，以R结尾
4）以L开头，以R结尾
1.4 尝试递归代码
public static int lpsl1(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] str = s.toCharArray();
return f(str, 0, str.length - 1);
}
// str[L..R]最长回文子序列长度返回
public static int f(char[] str, int L, int R) {
if (L == R) {
return 1;
}
if (L == R - 1) {
return str[L] == str[R] ? 2 : 1;
}
int p1 = f(str, L + 1, R - 1);
int p2 = f(str, L, R - 1);
int p3 = f(str, L + 1, R);
int p4 = str[L] != str[R] ? 0 : (2 + f(str, L + 1, R - 1));
return Math.max(Math.max(p1, p2), Math.max(p3, p4));
}
1.5 改动态规划分析
除了if (L == R) {
return 1;}
if (L == R - 1) {
return str[L] == str[R] ? 2 : 1;}
这两位置之后，其他位置的填的方法 从底往上填 每一行从左往右er
//跟进下面得图形推导出所求剩下得范围
for (int i = N - 3; i >= 0; i--)
for (int j = i + 2; j < N; j++)
1.6改动太规划代码
public static int longestPalindromeSubseq2(String s) {
if (s == null || s.length() == 0) {
return 0;
}
if (s.length() == 1) {
return 1;
}
char[] str = s.toCharArray();
int N = str.length;
int[][] dp = new int[N][N];
dp[N - 1][N - 1] = 1;
for (int i = 0; i < N - 1; i++) {
dp[i][i] = 1;
dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
//跟进上面得图形推导出所求剩下得范围
for (int i = N - 3; i >= 0; i--) {
for (int j = i + 2; j < N; j++) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
if (str[i] == str[j]) {
dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
}
}
}
return dp[0][N - 1];
}
}二 返回象棋从一个位置到另一个位置的方法有多少种
2.1 描述
请同学们自行搜索或者想象一个象棋的棋盘，
然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x，y，k
返回“马”从(0,0)位置出发，必须走k步
最后落在(x,y)上的方法数有多少种?
象棋走的日
2.2 分析 样本对应模型
跳的所有8方法
2.3 递归代码
// 当前来到的位置是（x,y）
// 还剩下rest步需要跳
// 跳完rest步，正好跳到a，b的方法数是多少？
// 10 * 9
public static int jump(int a, int b, int k) {
return process(0, 0, k, a, b);
}
public static int process(int x, int y, int rest, int a, int b) {
if (x < 0 || x > 9 || y < 0 || y > 8) {
return 0;
}
if (rest == 0) {
return (x == a && y == b) ? 1 : 0;
}
int ways = process(x + 2, y + 1, rest - 1, a, b);
ways += process(x + 1, y + 2, rest - 1, a, b);
ways += process(x - 1, y + 2, rest - 1, a, b);
ways += process(x - 2, y + 1, rest - 1, a, b);
ways += process(x - 2, y - 1, rest - 1, a, b);
ways += process(x - 1, y - 2, rest - 1, a, b);
ways += process(x + 1, y - 2, rest - 1, a, b);
ways += process(x + 2, y - 1, rest - 1, a, b);
return ways;
}2.4 改动态规划
是个三维数组，要的是rest的数据，rest要的数据是rest-1的数据 最终rest==0又是知道的
public static int dp(int a, int b, int k) {
int[][][] dp = new int[10][9][k + 1];
dp[a][b][0] = 1;
for (int rest = 1; rest <= k; rest++) {
for (int x = 0; x < 10; x++) {
for (int y = 0; y < 9; y++) {
int ways = pick(dp, x + 2, y + 1, rest - 1);
ways += pick(dp, x + 1, y + 2, rest - 1);
ways += pick(dp, x - 1, y + 2, rest - 1);
ways += pick(dp, x - 2, y + 1, rest - 1);
ways += pick(dp, x - 2, y - 1, rest - 1);
ways += pick(dp, x - 1, y - 2, rest - 1);
ways += pick(dp, x + 1, y - 2, rest - 1);
ways += pick(dp, x + 2, y - 1, rest - 1);
dp[x][y][rest] = ways;
}
}
}
return dp[0][0][k];
}
public static int pick(int[][][] dp, int x, int y, int rest) {
if (x < 0 || x > 9 || y < 0 || y > 8) {
return 0;
}
return dp[x][y][rest];
}
