动态规划进阶【2】

动态规划进阶

1 最长回文子序列 LeetCode - 516

https://leetcode.com/problems/longest-palindromic-subsequence/submissions/

给定一个字符串str，返回这个字符串的最长回文子序列长度
比如 ： str = “a12b3c43def2ghi1kpm”
最长回文子序列是“1234321”或者“123c321”，返回长度7

1.1 尝试

//最长回文子序列【尝试方法：递归】
public class PalindromeSubsequenceDemo {
    
    public static int lps1(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;
        }
        //第一种情况：既不以L开头，也不以R结尾
        int p1 = f(str, L+1, R-1);
        //以L开头， 不以R结尾
        int p2 = f(str, L, R-1);
        //不以L开头， 以R结尾
        int p3 = f(str, L+1, R);
        //以L开头，以R结尾【如果L==R，则+2】
        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
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

1.2 动态规划

//动态规划
public static int lpsl2(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    char[] str = s.toCharArray();
    int N = str.length;
    int[][] dp = new int[N][N];
    //二维数组：只要右上角位置，最右下角位置为1
    dp[N - 1][N - 1] = 1;
    for (int i = 0; i < N - 1; i++) {
        //L == R
        dp[i][i] = 1;
        //L == R - 1
        dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
    }
    //一般情况
    for (int L = N - 3; L >= 0; L--) {
        for (int R = L + 2; R < N; R++) {
            dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
            if (str[L] == str[R]) {
                dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
            }
        }
    }
    return dp[0][N - 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

2 象棋中"马"的走法

请同学们自行搜索或者想象一个象棋的棋盘，
然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
给你三个 参数 x，y，k
返回“马”从(0,0)位置出发，必须走k步
最后落在(x,y)上的方法数有多少种?

2.1 递归写法（尝试）

//当前位置：(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;
}
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

2.2 动态规划（三维）

三维动态规划表

//动态规划
//棋盘大小：10 * 9 [x * y]
//a, b 目标位置
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];
}
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

3 "喝咖啡"问题（京东面试题）

给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间
给定一个正数N，表示N个人等着咖啡机泡咖啡，每台咖啡机只能轮流泡咖啡
只有一台咖啡机，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯
每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发
假设所有人拿到咖啡之后立刻喝干净，
返回从开始等到所有咖啡机变干净的最短时间
三个参数：int[] arr、int N，int a、int b

拆分为两个子问题：先给人安排咖啡、再给人洗咖啡杯
思路：

1. 自定义Machine类（咖啡机）

2. 自义定比较器

3. 给人安排咖啡

4. 洗咖啡杯

3.1 暴力尝试

//咖啡机
public static class Machine {
    public int timePoint;//咖啡机初始可用时间点
    public int workTime;//咖啡机制作一杯咖啡所用时间

    public Machine(int t, int w) {
        this.timePoint = t;
        this.workTime = w;
    }
}

public static class MachineComparator implements Comparator<Machine> {

    @Override
    public int compare(Machine o1, Machine o2) {
        //为小跟堆做准备：谁的综合时间少，谁在前
        return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.workTime);
    }
}

/**
 *
 * @param arr 每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。
 * @param n 人数
 * @param a 咖啡机洗一杯需要的时间
 * @param b 自然挥发需要的时间
 * @return	所有人喝完咖啡，并且洗完杯子所花费的最少时间
 */
public static int minTime1(int[] arr, int n, int a, int b) {
    PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());
    for (int i = 0; i < arr.length; i++) {
        heap.add(new Machine(0, arr[i]));
    }
    int[] drinks = new int[n];
    for (int i = 0; i < n; i++) {
        Machine cur = heap.poll();
        cur.timePoint += cur.workTime;
        drinks[i] = cur.timePoint;
        heap.add(cur);
    }
    return bestTime(drinks, a, b, 0, 0);
}

//drinks 所有杯子可以开始洗的时间
//wash 单杯洗干净的时间（串行）
//air 挥发干净的时间（并行）
//free 洗的机器什么时候可用
//drinks[index...]都变干净， 最早的结束时间（返回）
public static int bestTime(int[] drinks, int wash, int air, int index, int free) {
    if (index == drinks.length) {
        return 0;
    }
    //index号杯子 决定洗
    int selfClean1 = Math.max(drinks[index], free) + wash;
    int restClean1 = bestTime(drinks, wash, air, index + 1, selfClean1);
    int p1 = Math.max(selfClean1, restClean1);

    //index号杯子决定挥发
    int selfClean2 = drinks[index] + air;
    int restClean2 = bestTime(drinks, wash, air, index + 1, free);
    int p2 = Math.max(selfClean2, restClean2);
    return Math.min(p1, 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

3.2 动态规划

//贪心+优良尝试改成动态规划
public static int minTime2(int[] arr, int n, int a, int b){
    PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());
    for(int i = 0; i < arr.length; i++) {
        heap.add(new Machine(0, arr[i]));
    }
    int[] drinks = new int[n];
    for(int i = 0; i < n; i++){
        Machine cur = heap.poll();
        //不断更新咖啡机可用时间点
        cur.timePoint += cur.workTime;
        drinks[i] = cur.timePoint;
        heap.add(cur);
    }
    return bestTimeDp(drinks, a, b);
}

//wash:洗咖啡所用时间
//air:挥发所用时间
//free的边界不好尝试：直接业务驱动->想象成最坏情况 -> 所以咖啡机全部走洗
public static int bestTimeDp(int[] drinks, int wash, int air){
    int N = drinks.length;
    int maxFree = 0;
    for(int i = 0; i < drinks.length; i++){
        maxFree = Math.max(maxFree, drinks[i]) + wash;
    }
    int[][] dp = new int[N+1][maxFree+1];
    //由递归可知：全部依赖于上一行【数组默认将最后一行填成了0】
    for(int index = N - 1; index >= 0; index--){
        for(int free = 0; free <= maxFree; free++){
            int selfClean1 = Math.max(drinks[index], free) + wash;
            if(selfClean1 > maxFree){
                break;//因为后面的不用填写了【递归不会调用到，类比：只要矩阵的左上半区】
            }
            //index号杯子 决定洗
            int restClean1 = dp[index+1][selfClean1];
            int p1 = Math.max(selfClean1, restClean1);
            //index号杯子 决定挥发
            int selfClean2 = drinks[index] + air;
            int restClean2 = dp[index+1][free];
            int p2 = Math.max(selfClean2, restClean2);
            dp[index][free] = Math.min(p1, p2);
        }
    }
    return dp[0][0];
}
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

4 最长公共子序列 LeetCode - 1143

给定两个字符串str1和str2，
返回这两个字符串的最长公共子序列长度

比如 ： str1 = “a12b3c456d”,str2 = “1ef23ghi4j56k”
最长公共子序列是“123456”，所以返回长度6

4. 1 递归尝试

//递归尝试
public static int longestCommonSubsequence1(String s1, String s2){
    if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    //尝试
    return process1(str1, str2, str1.length - 1, str2.length - 1);
}

//在str1的[0...i]与str2的[0...j]位置选出最长公共子序列
public static int process1(char[] str1, char[] str2, int i, int j){
    if(i == 0 && j == 0){
        return str1[i] == str2[j] ? 1 : 0;
    } else if( i == 0){
        if(str1[i] == str2[j]){
            return 1;
        } else {
            //i、j位置不相等，直接缩小范围也没影响
            return process1(str1, str2, i, j - 1);
        }
    } else if(j == 0){
        if(str1[i] == str2[j]){
            return 1;
        } else {
            return process1(str1, str2, i-1, j);
        }
    } else {
        //可能性1：i位置一定不要，j位置可要可不要
        int p1 = process1(str1, str2, i - 1, j);
        //可能性2：j位置一定不要，i位置可要可不要
        int p2 = process1(str1, str2, i, j-1);
        //可能性1、2会有重复值，但是我们是求最大值，因此对结果不会有影响【这种考虑方式是避免复杂的边界条件考虑】
        //可能性3:i、j位置都要
        int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
        return Math.max(p1, Math.max(p2, p3));
    }

}
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

4.2 动态规划

//动态规划
public static int longestCommonSubsequence2(String s1, String s2){
    if(s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0){
        return 0;
    }
    char[] str1 = s1.toCharArray();
    char[] str2 = s2.toCharArray();
    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 j = 1; j < M; j++){
        dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j-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];
            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(p2, p3));
        }
    }
    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