动态规划进阶【2】

﹏ヽ暗。殇╰゛Y 2024-04-07 15:08 89阅读 0赞

## 动态规划进阶 ##

### 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 动态规划 ####

//动态规划
    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];
    }

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

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

### 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);
    }

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

### 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));
        }
    
    }

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