算法|10.从暴力递归到动态规划3

灰太狼 2024-03-16 10:00 41阅读 0赞

## 算法|10.从暴力递归到动态规划3 ##

### 1.纸牌游戏 ###

题意：给定一个整型数组arr（都是正数），代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿。但是每个玩家每次只能拿走最左或最右的纸牌。玩家A和玩家B都绝顶聪明，请返回最后获胜者的分数。

**解题思路：**

*  “绝顶聪明”，意味着他们会尽可能保证自己拿的分数高，同时对手得到的分数低。
 *  这里分成了先手姿态和后手姿态

**核心代码：**

递归代码：

public static int win1(int[] arr) {
        
        if(arr==null||arr.length==0){
        
            return 0;
        }
        int first=f1(arr,0, arr.length-1);
        int second=g1(arr,0,arr.length-1);
        return Math.max(first,second);
    }
    
    public static int f1(int[] arr, int L, int R) {
        
         if(L==R){
        
             return arr[L];
         }
         int p1=arr[L]+g1(arr,L+1,R);
         int p2=arr[R]+g1(arr,L,R-1);
         return Math.max(p1,p2);
    }
    
    public static int g1(int[] arr, int L, int R) {
        
         if(L==R){
        
             return 0;
         }
         int p1=f1(arr,L+1,R);
         int p2=f1(arr,L,R-1);
         return Math.min(p1,p2);
    }

缓存的方法：

public static int win2(int[] arr) {
        
        if (arr == null || arr.length == 0) {
        
            return 0;
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
        
            for (int j = 0; j < N; j++) {
        
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr, 0, arr.length - 1, fmap, gmap);
        int second = g2(arr, 0, arr.length - 1, fmap, gmap);
        return Math.max(first, second);
    }
    
    // arr[L..R]，先手获得的最好分数返回
    public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        
        if (fmap[L][R] != -1) {
        
            return fmap[L][R];
        }
        int ans = 0;
        if (L == R) {
        
            ans = arr[L];
        } else {
        
            int p1 = arr[L] + g2(arr, L + 1, R, fmap, gmap);
            int p2 = arr[R] + g2(arr, L, R - 1, fmap, gmap);
            ans = Math.max(p1, p2);
        }
        fmap[L][R] = ans;
        return ans;
    }
    
    // // arr[L..R]，后手获得的最好分数返回
    public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap) {
        
        if (gmap[L][R] != -1) {
        
            return gmap[L][R];
        }
        int ans = 0;
        if (L != R) {
        
            int p1 = f2(arr, L + 1, R, fmap, gmap); // 对手拿走了L位置的数
            int p2 = f2(arr, L, R - 1, fmap, gmap); // 对手拿走了R位置的数
            ans = Math.min(p1, p2);
        }
        gmap[L][R] = ans;
        return ans;
    }

dp代码：

public static int win3(int[] arr) {
        
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for (int i = 0; i < N; i++) {
        
            fmap[i][i] = arr[i];
        }
        for (int startCol = 1; startCol < N; startCol++) {
        
            int L = 0;
            int R = startCol;
            while (R < N) {
        
                fmap[L][R] = Math.max(arr[L] + gmap[L + 1][R], arr[R] + gmap[L][R - 1]);
                gmap[L][R] = Math.min(fmap[L + 1][R], fmap[L][R - 1]);
                L++;
                R++;
            }
        }
        return Math.max(fmap[0][N - 1], gmap[0][N - 1]);
    }

**测试代码：**

public static void main(String[] args) {
        
        int[] arr = {
         5, 7, 4, 5, 8, 1, 6, 9,10,3, 4,100, 6, 1, 7 };
        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));
    
    }

**测试结果：**![在这里插入图片描述][a60ec836d836428dafbaac79cc7513f1.png]

### 2.最长回文子串 ###

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

**解题思路：**

*  剩余的个数为1，返回1
 *  剩余的个数为2，返回2
 *  否则分都要，要左边，要右边，两边都要四种情况，最终取最大值
 *  以上分类均给予坐标LR之间的关系

**核心代码：**

递归代码：

public static int lps(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 (R - L == 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));
    }

dp代码：

public static int dp(String s) {
        
        if (s == null || s.length() == 0) {
        
            return 0;
        }
        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 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];
    }

**测试**：[测试链接][Link 1]

### 区间范围尝试模型总结 ###

**改写dp：**

**例题总结：**

[a60ec836d836428dafbaac79cc7513f1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ddc36b46490442aebe719b6f2ed94089.png
[Link 1]: https://leetcode.com/problems/longest-palindromic-subsequence/