算法11.从暴力递归到动态规划4

算法|11.从暴力递归到动态规划4

1.最长公共子序列

题意：给定两个字符串str1和str2，返回这两个字符串的最长公共子序列长度
比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
最长公共子序列是“123456”，所以返回长度6

解题思路：

• 每个字符串都有一个指针，两个可变参数
• 边界条件——两个指针都为0时；第一个为0时；第二个为0时。因为决策方向是从右向左
• 子过程分析的时候有四种情况：str1当前不要str2当前不要；str1当前不要str2要；str1当前要str2不要；str1和str2当前都要
• 取四种情况的最大值

核心代码：

递归代码：

private static int lsc(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        return process(str1, str2, str1.length - 1, str2.length - 1);
    }

    /**
     * @param str1
     * @param str2
     * @param i:str1考虑[0..i]
     * @param j:str2考虑[0..j]
     * @return
     */
    private static int process(char[] str1, char[] str2, int i, int j) {
        if (i == 0 && j == 0) {
            return str1[i] == str2[j] ? 1 : 0;
        } else if (i == 0) {
            return str1[0] == str2[j] ? 1 : process(str1, str2, i, j - 1);
        } else if (j == 0) {
            return str1[i] == str2[0] ? 1 : process(str1, str2, i - 1, j);
        } else {
//            int p4=process(str1,str2,i-1,j-1);决策四不写是因为已经知道4一定干不过1和2,所以直接不写，不考虑这种可能性
            int p1 = process(str1, str2, i - 1, j);
            int p2 = process(str1, str2, i, j - 1);
            int p3 = str1[i] == str2[j] ? 1 + process(str1, str2, i - 1, j - 1) : 0;
            return Math.max(p1, Math.max(p3, p2));
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

dp代码：

private static int dp(String s1, String s2) {
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    //由尝试可以知道，可变参数为每次开始决策的下标位置，且范围分别是两个数组的长度-1，所以这里抓一下
    int N = str1.length;
    int M = str2.length;
    int[][] dp = new int[N][M];
    //由尝试的base case可以看出，依赖关系是右依赖左，初始条件是第一行第一列
    dp[0][0] = str1[0] == str2[0] ? 1 : 0;
    //第一行
    for (int i = 1; i < M; i++) {
        dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
    }
    //第一列
    for (int i = 1; i < N; i++) {
        dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
    }
    //普遍位置:按行从左到右
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < M; j++) {
            int p1 = dp[i - 1][j];//在这里因为行列不对应，参数j是0-5,但是数组是0-3,所以有个越界问题，依赖的思路从列变成行即可
            int p2 = dp[i][j - 1];
            int p3 = str1[i] == str2[j] ? 1 + dp[i - 1][j - 1] : 0;
            dp[i][j] = Math.max(p1, Math.max(p3, p2));
        }
    }
    return dp[N - 1][M - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

测试代码：略

测试结果：

2.分裂数字问题

题意：给定一个正数n，求n的裂开方法数，规定：后面的数不能比前面的数小
比如4的裂开方法有：1+1+1+1、1+1+2、1+3、2+2、4。5种，所以返回5

解题思路：

核心代码：

递归代码：

public static int ways(int n){
    if(n<0){
        return 0;
    }
    if(n==1){
        return 1;
    }
    return process(1,n);//为什么不是1,n-1
}

/**
 *
 * @param pre 上一个拆出来的数
 * @param rest 还剩rest需要拆
 * @return 返回拆解的方法数
 */
public static int process(int pre,int rest){
    //base case 这条路走不通  pre=3  rest=2（前置的数比后边的数大）
    if(rest==0){
        return 1;
    }
    if(pre>rest){
        return 0;
    }
    if(pre==rest){//相等的时候就提前结束
        return 1;
    }
    int ways=0;
    for (int first=pre;first <=rest ; first++) {//(2,7)的例子
        ways+=process(first,rest-first);
    }
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

dp代码：

public static int dp(int n){
    if(n<0){
        return 0;
    }
    if(n==1){
        return 1;
    }
    int[][] dp=new int[n+1][n+1];
    for (int pre = 1; pre <= n; pre++) {
        dp[pre][0] = 1;
        dp[pre][pre] = 1;
    }
    for (int pre = n-1; pre >=1 ; pre--) {//第n行已经填好了，第0号无效，从n-1行到第1行
        for (int rest = pre+1; rest <=n ; rest++) {//pre的位置已经填过了
            int ways=0;
            for (int first=pre;first <=rest ; first++) {//(2,7)的例子
                ways+=dp[first][rest-first];
            }
            dp[pre][rest]=ways;
        }
    }
    return dp[1][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

测试代码：略

测试结果：

3.Bob生存概率问题

题意：给定5个参数，N，M，row，col，k
表示在NM的区域上，醉汉Bob初始在(row,col)位置
Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
任何时候Bob只要离开NM的区域，就直接死亡
返回k步之后，Bob还在N*M的区域的概率

解题思路：

• 概率问题也可以动态规划问题，算出的总方法数/总的个数（4^k次方）
• 问题转换成动态规划，转化成实验，收集生存点数
• 可变参数有三个，分别是行列剩余的步数
• 子过程中边界条件有行列有效判定，有rest=0两个边界
• 子过程分析有四个情况，返回四种情况下的总方法数

核心代码：

递归代码：

public static double livePosibility1(int row,int col,int k,int N,int M){
    return (double)process(row,col,k,M,N)/Math.pow(4,k);
}

/**
 *
 * @param row 当前在(row,col)位置，
 * @param col
 * @param rest 走完k步，如果还在棋盘就获得一个生存点
 * @param m 棋盘的大小是n行m列
 * @param n
 * @return
 */
private static long process(int row, int col, int rest, int n, int m) {
    //这里就相当于是走出去了，剪枝了，获得生存点数0
    if(row<0||row==n||col<0||col==m){
        return 0;
    }
    //base case
    if(rest==0){
        return 1;
    }
    //普遍问题
    long up=process(row-1,col,rest-1,n,m);
    long down=process(row+1,col,rest-1,n,m);
    long left=process(row,col-1,rest-1,n,m);
    long right=process(row,col+1,rest-1,n,m);
    return up+down+left+right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

dp代码：

public static double livePosibility2(int row,int col,int k,int n,int m){
    if(row<0||row==n||col<0||col==m){
        return 0;
    }
    long[][][] dp=new long[n][m][k+1];
    //这里边只要还在范围内，就有一个生命值
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            dp[i][j][0] = 1;
        }
    }
    //这里x-y的范围是0~边界-1
    for (int rest = 1; rest <=k ; rest++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //                    这里也是需要判断越界，同象棋跳马一样，所以采用pick方法
                dp[i][j][rest]+=pick(dp,i-1,j,rest-1,n,m);
                dp[i][j][rest]+=pick(dp,i+1,j,rest-1,n,m);
                dp[i][j][rest]+=pick(dp,i,j-1,rest-1,n,m);
                dp[i][j][rest]+=pick(dp,i,j+1,rest-1,n,m);
            }
        }
    }
    return (double)dp[row][col][k]/Math.pow(4,k);
}

private static long pick(long[][][] dp, int i, int j, int k,int n,int m) {
    if(i<0||j<0||k<0||i>=n||j>=m||k<0){
        return 0;
    }
    return dp[i][j][k];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

测试代码：

public static void main(String[] args) {
    System.out.println(livePosibility1(6, 6, 10, 50, 50));
    System.out.println(livePosibility2(6, 6, 10, 50, 50));
}
1
2
3
4

测试结果：

4.砍死怪兽概率问题

题意：给定3个参数，N，M，K，怪兽有N滴血，等着英雄来砍自己
英雄每一次打击，都会让怪兽流失[0_{M]的血量，到底流失多少？每一次在[0}M]上等概率的获得一个值，求K次打击之后，英雄把怪兽砍死的概率

解题思路：

• 总方法数是M+1次展开，M+1层
• 同上，这里是实验问题
• 可变参数有三个N,M,K，返回的是k次之后怪兽存活的方法数

核心代码：

递归代码：

public static double right(int N,int M,int K){
    if(N<1||M<1||K<1){
        return 0;
    }
    long all=(long) Math.pow(M+1,K);
    long kill=process(K,M,N);
    return (double) kill/all;
}

/**
 *
 * @param times 剩余的次数
 * @param M 每次伤害的最高值
 * @param hp 剩余的生命值
 * @return
 */
private static long process(int times, int M, int hp) {
     if(times==0){
         return hp<=0?1:0;
     }
     //但是这里好像又是一个剪枝，当现在已经小于等于0了，那么这条支路下边的展开必然是满足题意的
     if(hp<=0){
         //返回的方法数就应该是这样
         return (long)Math.pow(M+1,times);
     }
     long ways=0;
     //普遍情况
    for (int i = 0; i <=M ; i++) {
        ways+=process(times-1,M,hp-i);
    }
    return ways;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

dp代码：

private static double dp(int K, int M, int N) {
        if(N<1||M<1||K<1){
            return 0;
        }
        long all=(long) Math.pow(M+1,K);
        long[][] dp=new long[K+1][N+1];
        //hp都没了还砍只存在于尝试思路，但是最后也是剪掉了
        dp[0][0]=1;
        for (int times = 1; times <= K ; times++) {
            dp[times][0] = (long) Math.pow(M + 1, times);
            for (int hp = 1; hp <=N ; hp++) {

                long ways=0;
                for (int i = 0; i <=M ; i++) {
//                    这里边hp-i可能会越界，所以需要分情况讨论一下
//                    ways+=dp[times-1][hp-i];
                    if(hp-i>=0){
                        ways+=dp[times-1][hp-i];
                    }else{
                        ways+=(long)Math.pow(M+1,times-1);
                    }
                }
                dp[times][hp]=ways;
            }
        }
        return (double)dp[K][N]/all;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

测试代码：略

测试结果：

5.最长回文子串

题意前边已经说过，这里只是另一种解法，所以只放代码了。

这里的思路是拿到原串的逆串，并且将这两个串作为最大公共子串的参数，这里就是使用样本对应尝试模型了。

核心代码：

public static int lps(String s){
    if(s==null||s.length()==0){
        return 0;
    }
    if(s.length()==1){
        return 1;
    }
    char[] str1=s.toCharArray();
    char[] str2=reverse(str1);
    return process(str1,str2,str1.length-1,str2.length-1);
}
private static char[] reverse(char[] s) {
    char[] str=new char[s.length];
    for (int i = 0; i < s.length; i++) {
        str[i]=s[s.length-1-i];
    }
    return str;
}

private static int process(char[] str1, char[] str2, int i, int j) {
    if(i==0&&j==0){
        return str1[i]==str2[j]?1:0;
    }else if(i==0){
        return str1[0]==str2[j]?1: process(str1,str2,i,j-1);
    }else if(j==0){
        return str1[i]==str2[0]?1: process(str1,str2,i-1,j);
    }else{
        int p1= process(str1,str2,i-1,j);
        int p2= process(str1,str2,i,j-1);
        int p3=str1[i]==str2[j]?1+ process(str1,str2,i-1,j-1):0;
        return Math.max(p1,Math.max(p3,p2));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

测试代码：

public static String randomString(int len) {
    char[] str = new char[len];
    for (int i = 0; i < len; i++) {
        str[i] = (char) ((int) (Math.random() * 10) + 'a');
    }
    return String.valueOf(str);
}
private static int dp(String s) {
    if(s==null||s.length()==0){
        return 0;
    }
    char[] str=s.toCharArray();
    //可变参数范围为0-N-1，所以抓虾数组长度
    int N=str.length;
    int[][] dp=new int[N][N];
    dp[N-1][N-1]=1;
    //由两个base case 可以得出第一条对角线和挨着的斜线，另外可以得知主对角线下的数据没意义
    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--) {//从倒数第三列开始（别忘了边界坐标是N-1）
        //一条斜线一条斜线弄的
        for (int j = i+2; j < N ; j++) {//起始位置得推，暂时先记着
            int p1=dp[i+1][j-1];
            int p2=dp[i+1][j];
            int p3=dp[i][j-1];
            int p4=str[i]==str[j]?2+dp[i+1][j-1]:0;
            dp[i][j]=Math.max(Math.max(p1,p2),Math.max(p4,p3));//有次因为这里的最大值没改过来一直错
        }

    }
    return dp[0][N-1];
}

public static void main(String[] args) {
    int len = 10;
    int testTime = 1000;
    System.out.println("测试开始");
    for (int i = 0; i < testTime; i++) {
        String s = randomString(len);
        int ans0 = lps(s);
        int ans1 = dp(s);
        if (ans0 != ans1) {
            System.out.println(s);
            System.out.println(ans0);
            System.out.println(ans1);
            System.out.println("Oops!");
            break;
        }
    }
    System.out.println("测试结束");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

样本对应尝试模型总结

改写Dp：

• 无法改写成dp，不是因为是字符串，而是之前那个贴纸问题可能性太多了，而这个最长公共子序列同样是两个字符串，但是极限可能也是两个字符串中最大的长度相同。
• 概率问题，其实可以通过实验获得生存点数，然后除以总可能展开的点数，可以得到计算
• 最长公共子序列和最长回文子串问题都可以通过样本对应尝试模型完成

例题总结：

• 最长公共子序列——四种情况（00,10,01,11）；边界条件(i=0,j=0,i=0&j=0)
• 分裂数字问题
• Bob生存概率问题——边界条件rest、位置有效性；四种可能收集总情况
• 砍死怪兽概率问题——边界条件、位置有效性；可能收集总情况（略）
• 最长回文子串——逆串+调用最长公共子序列函数