动态规划每日一练（四）

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