动态规划每日一练（四）
一、day1——最长数对链
题目链接：
646. 最长数对链 - 力扣（LeetCode）646. 最长数对链 - 给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。找出并返回能够形成的 最长数对链的长度 。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。 示例 1：输入：pairs = [[1,2], [2,3], [3,4]]输出：2解释：最长的数对链是 [1,2] -> [3,4] 。示例 2：输入：pairs = [[1,2],[7,8],[4,5]]输出：3解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。 提示： * n == pairs.length * 1 <= n <= 1000 * -1000 <= lefti < righti <= 1000https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/595118336/https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/595118336/https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/595118336/https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/595118336/
https://leetcode.cn/problems/maximum-length-of-pair-chain/submissions/595118336/
解题思路：
代码实现：
class Solution { public int findLongestChain(int[][] pairs) { int n = pairs.length; Arrays.sort(pairs, (a, b) -> a[0] - b[0]); // 1.创建dp表 int[] dp = new int[n]; // 2.初始化 for (int i = 0; i < n; i++) { dp[i] = 1; } // 3.填表 int maxLength = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (pairs[j][1] < pairs[i][0]) { dp[i] = dp[j] + 1; } if (dp[i] > maxLength) maxLength = dp[i]; } } // 4.返回值 return maxLength; } }
二、day2——最长定差子序列
题目链接：
1218. 最长定差子序列 - 力扣（LeetCode）1218. 最长定差子序列 - 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。 示例 1：输入：arr = [1,2,3,4], difference = 1输出：4解释：最长的等差子序列是 [1,2,3,4]。示例 2：输入：arr = [1,3,5,7], difference = 1输出：1解释：最长的等差子序列是任意单个元素。示例 3：输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2输出：4解释：最长的等差子序列是 [7,5,3,1]。 提示： * 1 <= arr.length <= 105 * -104 <= arr[i], difference <= 104https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/
解题思路：
代码实现：
class Solution { public int longestSubsequence(int[] arr, int difference) { Map<Integer, Integer> hash = new HashMap(); int ret = 1; int maxLength = 1; for (int a : arr) { hash.put(a, hash.getOrDefault(a - difference, 0) + 1); if (maxLength < hash.get(a)) maxLength = hash.get(a); } return maxLength; } }
三、day3——最长斐波那契子序列的长度
题目链接：
LCR 093. 最长的斐波那契子序列的长度 - 力扣（LeetCode）LCR 093. 最长的斐波那契子序列的长度 - 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的： * n >= 3 * 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列） 示例 1：输入: arr = [1,2,3,4,5,6,7,8]输出: 5解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。示例 2：输入: arr = [1,3,7,11,12,14,18]输出: 3解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。 提示： * 3 <= arr.length <= 1000 * 1 <= arr[i] < arr[i + 1] <= 10^9 注意：本题与主站 873 题相同： https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/ [https://leetcode-cn.com/problems/length-of-longest-fibonacci-subsequence/]https://leetcode.cn/problems/Q91FMA/description/https://leetcode.cn/problems/Q91FMA/description/https://leetcode.cn/problems/Q91FMA/description/https://leetcode.cn/problems/Q91FMA/description/https://leetcode.cn/problems/Q91FMA/description/
解题思路：
代码实现：
class Solution { public int lenLongestFibSubseq(int[] arr) { Map<Integer,Integer> hash = new HashMap<>(); int n = arr.length; for(int i = 0;i<n;i++) hash.put(arr[i],i); //1.创建dp表 int[][] dp = new int[n][n]; //2.初始化 for(int i = 0;i<n;i++) for(int j = 0;j<n;j++) dp[i][j] = 2; //3.填表 int ret = 2; for(int j = 2;j<n;j++){ for(int i = 1;i<j;i++){ int a = arr[j] - arr[i]; if(a<arr[i] && hash.containsKey(a)){ dp[i][j] = dp[hash.get(a)][i] + 1; } ret = Math.max(ret,dp[i][j]); } } //4返回值 return ret < 3 ? 0 : ret; } }
四、day4——最长等差数列
题目链接：
1027. 最长等差数列 - 力扣（LeetCode）1027. 最长等差数列 - 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。 示例 1：输入：nums = [3,6,9,12]输出：4解释： 整个数组是公差为 3 的等差数列。示例 2：输入：nums = [9,4,7,2,10]输出：3解释：最长的等差子序列是 [4,7,10]。示例 3：输入：nums = [20,1,15,3,10,5,8]输出：4解释：最长的等差子序列是 [20,15,10,5]。 提示： * 2 <= nums.length <= 1000 * 0 <= nums[i] <= 500https://leetcode.cn/problems/longest-arithmetic-subsequence/https://leetcode.cn/problems/longest-arithmetic-subsequence/https://leetcode.cn/problems/longest-arithmetic-subsequence/https://leetcode.cn/problems/longest-arithmetic-subsequence/
解题思路：
代码实现：
class Solution { public int longestArithSeqLength(int[] nums) { Map<Integer,Integer> hash = new HashMap<>(); int n = nums.length; hash.put(nums[0],0); //1.创建dp表 int[][] dp = new int[n][n]; //2.初始化 for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ dp[i][j] = 2; } } //3.填表 int ret = 2; for(int i = 1; i<n;i++)//固定倒数第二个数 { for(int j = i + 1;j<n;j++){ int a = 2*nums[i] - nums[j]; if(hash.containsKey(a)){ dp[i][j] = dp[hash.get(a)][i] + 1; ret = Math.max(ret,dp[i][j]); } } hash.put(nums[i],i); } //4.返回值 return ret; } }
五、day5——等差数列划分II
题目链接：
446. 等差数列划分 II - 子序列 - 力扣（LeetCode）446. 等差数列划分 II - 子序列 - 给你一个整数数组 nums ，返回 nums 中所有 等差子序列 的数目。如果一个序列中 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该序列为等差序列。 * 例如，[1, 3, 5, 7, 9]、[7, 7, 7, 7] 和 [3, -1, -5, -9] 都是等差序列。 * 再例如，[1, 1, 2, 5, 7] 不是等差序列。数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。 * 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。题目数据保证答案是一个 32-bit 整数。 示例 1：输入：nums = [2,4,6,8,10]输出：7解释：所有的等差子序列为：[2,4,6][4,6,8][6,8,10][2,4,6,8][4,6,8,10][2,4,6,8,10][2,6,10]示例 2：输入：nums = [7,7,7,7,7]输出：16解释：数组中的任意子序列都是等差子序列。 提示： * 1 <= nums.length <= 1000 * -231 <= nums[i] <= 231 - 1https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/
解题思路：
代码实现：
!!!注释的代码为优化代码，未注释的为原始方法，即i内每次循环都遍历一次nums数组
class Solution { public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; // Map<Long,List<Integer>> hash = new HashMap<>(); // for(int i = 0;i < n;i++){ // long tmp =(long)nums[i]; // if(!hash.containsKey(tmp)){ // hash.put(tmp,new ArrayList<Integer>()); // } // hash.get(tmp).add(i); // } // 1.创建dp表 int[][] dp = new int[n][n]; // 2.初始化 // 3.填表 int count = 0; for (int j = 2; j < n; j++) { for (int i = 1; i < j; i++) { long a = 2L * nums[i] - nums[j]; // if(hash.containsKey(a)){ // for(int k:hash.get(a)){ // if(k<i) dp[i][j] += dp[k][i] + 1; // else break; // } // } for (int k = 0; k < i; k++) { if (nums[k] == a) { dp[i][j] += dp[k][i] + 1; } } count += dp[i][j]; } } // 4.返回值 return count; } }
六、day6——回文子串
题目链接：
LCR 020. 回文子串 - 力扣（LeetCode）LCR 020. 回文子串 - 给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。 示例 1：输入：s = "abc"输出：3解释：三个回文子串: "a", "b", "c"示例 2：输入：s = "aaa"输出：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 提示： * 1 <= s.length <= 1000 * s 由小写英文字母组成 注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/palindromic-substrings/ [https://leetcode-cn.com/problems/palindromic-substrings/] https://leetcode.cn/problems/a7VOhD/https://leetcode.cn/problems/a7VOhD/https://leetcode.cn/problems/a7VOhD/
解题思路：
代码实现：
class Solution { public int countSubstrings(String ss) { int n = ss.length(); char[] s = ss.toCharArray(); // 1.创建dp表 boolean[][] dp = new boolean[n][n]; // 2.初始化——不用 // 3.填表 int count = 0; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if(s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true; if (dp[i][j] == true) count++; } } // 4返回值 return count; } }
七、day7——最长回文串
题目链接：
409. 最长回文串 - 力扣（LeetCode）409. 最长回文串 - 给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的 回文串 的长度。在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。 示例 1:输入:s = "abccccdd"输出:7解释:我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。示例 2:输入:s = "a"输出:1解释：可以构造的最长回文串是"a"，它的长度是 1。 提示: * 1 <= s.length <= 2000 * s 只由小写 和/或 大写英文字母组成https://leetcode.cn/problems/longest-palindrome/description/https://leetcode.cn/problems/longest-palindrome/description/
解题思路：
代码实现：
class Solution { public String longestPalindrome(String ss) { int n = ss.length(); char[] s = ss.toCharArray(); // 1.创建dp表 boolean[][] dp = new boolean[n][n]; // 2.初始化——不用 // 3.填表 String maxLength = ""; for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true; if (dp[i][j] == true) if(maxLength.length() < j - i + 1) maxLength = ss.substring(i,j+1); } } // 4返回值 return maxLength; } }
八、day8——分割回文串IV
题目链接：
1745. 分割回文串 IV - 力扣（LeetCode）1745. 分割回文串 IV - 给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。 示例 1：输入：s = "abcbdd"输出：true解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。示例 2：输入：s = "bcbddxy"输出：false解释：s 没办法被分割成 3 个回文子字符串。 提示： * 3 <= s.length <= 2000 * s 只包含小写英文字母。https://leetcode.cn/problems/palindrome-partitioning-iv/description/https://leetcode.cn/problems/palindrome-partitioning-iv/description/
解题思路：
代码实现：
class Solution { public boolean checkPartitioning(String ss) { int n = ss.length(); char[] s = ss.toCharArray(); // 1.创建dp表 boolean[][] dp = new boolean[n][n]; // 2.初始化——不用 // 3.填表 for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true; } } // 4返回值 for (int i = 1; i < n - 1; i++) { for (int j = i; j < n - 1; j++) { if (dp[0][i - 1] == true && dp[i][j] == true && dp[j + 1][n - 1] == true) return true; } } return false; } }
九、day9——分割回文串II
题目链接：
132. 分割回文串 II - 力扣（LeetCode）132. 分割回文串 II - 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的 最少分割次数 。 示例 1：输入：s = "aab"输出：1解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。示例 2：输入：s = "a"输出：0示例 3：输入：s = "ab"输出：1 提示： * 1 <= s.length <= 2000 * s 仅由小写英文字母组成https://leetcode.cn/problems/palindrome-partitioning-ii/https://leetcode.cn/problems/palindrome-partitioning-ii/
解题思路：
代码实现：
class Solution { public int minCut(String ss) { int n = ss.length(); char[] s = ss.toCharArray(); //1.创建dp表 int[] dp1 = new int[n]; boolean [][] dp2 = new boolean[n][n]; //2.初始化 for(int i = 0;i < n;i++) dp1[i] = Integer.MAX_VALUE; //3.填表 for(int i = n-1;i >=0 ;i--){ for(int j = i;j < n;j++){ if(s[i] == s[j]) dp2[i][j] = i+1 < j ? dp2[i+1][j-1] : true; } } for(int i = 0;i< n;i++){ if(dp2[0][i]){ dp1[i] = 0; }else{ for(int j = 1;j <= i;j++){ if(dp2[j][i]){ dp1[i] = Math.min(dp1[i] , dp1[j-1] + 1); } } } } return dp1[n-1]; } }
十、day10——最长回文子序列
题目链接：
516. 最长回文子序列 - 力扣（LeetCode）516. 最长回文子序列 - 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 示例 1：输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。示例 2：输入：s = "cbbd"输出：2解释：一个可能的最长回文子序列为 "bb" 。 提示： * 1 <= s.length <= 1000 * s 仅由小写英文字母组成https://leetcode.cn/problems/longest-palindromic-subsequence/
解题思路：
代码实现：
class Solution { public int longestPalindromeSubseq(String ss) { int n = ss.length(); char[] s = ss.toCharArray(); //1.创建dp表 int[][] dp = new int[n][n]; //2.初始化——不用 //3.填表 for(int i = n-1;i>=0;i--){ for(int j = i;j<n;j++){ if(s[i] == s[j]){ if(i==j) dp[i][j] = 1; else if(i+1 == j) dp[i][j] = 2; else dp[i][j] = dp[i+1][j-1] + 2; }else{ dp[i][j] = Math.max(dp[i][j-1] , dp[i+1][j]); } } } //4.返回值 return dp[0][n-1]; } }