当前位置：首页 > news >正文

算法体系-21 第二十一暴力递归到动态规划（三）

news 来源：原创 2024/6/25 14:07:15

一最长回文子串

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 * 9public 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];}