【leetcode】动态规划

28. 673. 最长递增子序列个数

题目：

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

题目链接

673. 最长递增子序列的个数 - 力扣（LeetCode）

文字分析

 代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> dp(n,1);
        vector<int>count(n,1);
        int Max = 0;
        int len = 1;
        for(int i = 1;i < n;i++)
        {
            for(int j = i - 1;j >= 0;j--)
            {
                if(nums[i] > nums[j])
                {
                    int x = dp[j] + 1;
                    if(dp[i] > x)
                    {
                        ;
                    }
                    else if(dp[i] == x)
                    {
                        count[i] += count[j] ;
                    }
                    else
                    {
                        dp[i] = x;
                        count[i] = count[j];
                    }
                }
            }
             len = max(len,dp[i]);
        }
       for(int i = 0;i < n;i++)
       {
          if(dp[i] == len)
          {
            Max += count[i];
          }
       }
        return Max;
    }
};

29. 646. 最长数队链

题目：

给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。

现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。

找出并返回能够形成的 最长数对链的长度 。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

题目链接

646. 最长数对链 - 力扣（LeetCode）

文字分析

这里由于无顺序，导致按子序列的返回求不了，并且也不好填dp表，因为dp表是有一定顺序去填的

所以这里我们需要对原数组排序

vector<int>的排序规则：

默认优先对第一元素进行排列，第一元素相同，再比第二元素

符合我们需要的排序

这里发现比较 只需要比较nums[i][1] 和 nums[j][0]的大小关系，即可判断是否构成数队链

剩下的解法参考 26.最长递增子序列

代码

class Solution 
{
public:
    int findLongestChain(vector<vector<int>>& pairs) 
    {
           int n =  pairs.size();
           sort(pairs.begin(),pairs.end());
           vector<int> dp(n,1);
           int Max = 1;
           for(int i = 1;i < n;i++)
           {
               for(int j = i - 1;j >= 0;j--)
               {
                  if(pairs[i][0] > pairs[j][1])
                  {
                    dp[i] = max(dp[i],dp[j] + 1);
                  }
               }
               Max = max(Max,dp[i]);
           }
           return Max;
    }
};

30. 1218. 最长定差子序列

题目：

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

题目链接

1218. 最长定差子序列 - 力扣（LeetCode）

文字分析

主要解题思路参考 26. 最长递增子序列

这道题有一点特殊：

它是定差的

因此，我们通过 num[i] ， 就可以知道它构成的子序列中，上一个元素是谁（nums[i] - difference)

通过这一点，我们来进行优化：

通过 元素 + dp[i] 的方式组合在一起，存在哈希表里面

只需要知道上一个元素在不在，从而判断dp[i]的值

初始化 ：hash[nums[0]] = 1 （这里不能用数组，nums里的值可能小于0）

nums[i] : 以 i 位置这个元素结尾， hash[nums[i]] 存放 以 i 位置这个元素结尾得到的最长子序列长度，即dp[i]

代码

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        int Max = 1;
        int n = arr.size();
        unordered_map<int,int> hash;
        hash[arr[0]] = 1;
        for(int i = 1;i < n;i++)
        {
            int x = arr[i] - difference;
            if(hash[x] == 0)
            {
               hash[arr[i]] = 1;
            }
            else
            {
                hash[arr[i]] = hash[x] + 1;
            }
            Max = max(Max,hash[arr[i]]);
        }
        return Max;
    }    
};