算法

您所在的位置：网站首页 › 动态规划和递归算法的区别 › 算法

算法

2023-06-26 17:05| 来源: 网络整理| 查看: 265

算法|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 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 int L = 0; int R = startCol; while (R 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)); }

测试结果：在这里插入图片描述

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 for (int R = L + 2; R dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]); } } } return dp[0][N - 1]; }

测试：测试链接

区间范围尝试模型总结

改写dp：

例题总结：

【本文地址】

算法

算法

今日新闻

推荐新闻