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

一 最长回文子串

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];
    }