动态规划每日一练（四）

一、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];}
}