刷题之动态规划-子序列

前言

大家好，我是jiantaoyab，开始刷动态规划的子序列类型相关的题目，子序列元素的相对位置和原序列的相对位置是一样的

动态规划5个步骤

状态表示：dp数组中每一个下标对应值的含义是什么>dp[i]表示什么
状态转移方程： dp[i] 等于什么
1 和 2 是动态规划的核心步骤，第三步是初始化，保证填表的时候不越界
填表顺序：为了保证填写当前状态的时候，所需要的状态已经计算过
返回值

最长递增子序列

题目分析

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int ret = 1;
    for(int i = 1; i < n; i++)
    {
      for(int k = 0; k < i; k++)
      {
        if(nums[k] < nums[i])
        dp[i] = max(dp[k] + 1, dp[i]);
      }
      ret = max(ret, dp[i]);
    }
  
    return ret;
  }
};

摆动序列

代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
      int n = nums.size();
      vector<int> f(n, 1); 
      vector<int> g(n, 1);
      int ret = 1;
      for(int i = 1; i < n; i++)
      {
        for(int j = 0; j < i; j++)
        {
          if(nums[j] < nums[i])
          //递增
          f[i] = max(f[i],  g[j] + 1); 
          else if(nums[j] > nums[i])
          //递减 
          g[i] = max(g[i],  f[j] + 1);
        }   
        ret = max(f[i], g[i]);
      }
      return ret ;

    }
};

最长递增子序列的个数

题目分析

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len(n, 1);
        vector<int> count(n, 1);
        int ret_len = 1, ret_count = 1;
        for(int i = 1; i < n; i++)
        {
          for(int k = 0; k < i; k++)
          {
            if(nums[k] < nums[i]) 
            {
              if(len[k] + 1 == len[i]) count[i] += count[k];
              else if(len[k] + 1 > len[i])
              {
                len[i] = len[k] + 1 ; count[i] = count[k];
              }
              
            }                 
          }
          //更新返回值
          if(ret_len == len[i]) ret_count += count[i];
          else if(ret_len < len[i]) ret_len = len[i], ret_count = count[i];
         
        }
        return  ret_count;
        
    }
};

最长数对链

题目分析

dp[i]: 表示以i位置为结尾的最长数对链的长度

在（0，i-1）中取一个j,是数对链的话得满足pairs[j] [1] < pairs[i] [0]

代码

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int m = pairs.size();
        vector<int> dp (m, 1);
        sort(pairs.begin(), pairs.end());

        int ret = 1;
        for(int i = 1; i < m; i++)
        {
          for(int j = 0; j < i; j++)
          {
            if(pairs[j][1] < pairs[i][0])
            dp[i] = max(dp[j] + 1, dp[i]);
          }
          ret = max(ret, dp[i]);
        }
       return ret;
    }
};

最长定差子序列

题目分析

代码

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n  = arr.size();
        unordered_map<int, int> hash; //<arr[i], dp[i]>
        int ret = 1;
        //初始化
        hash[arr[0]] = 1;
        for(int i = 1; i < n; i++)
        {
          hash[arr[i]] = hash[arr[i] - difference] + 1;
          ret = max(ret, hash[arr[i]]);
        }
        return ret;
    }
};

最长的斐波那契子序列的长度

题目分析

代码

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
      
        int n = arr.size();
        vector<vector<int>> dp(n, vector<int>(n, 2));
        unordered_map<int, int> hash;
        //将arr中的值和下标绑定起来
        for(int i = 0; i < n; i++) hash[arr[i]] = i;
        int ret = 2;
        for(int j = 2; j < n; j++) //固定最后一个位置
        {
          for(int i = 1; i < j; i++) //固定倒数第二个位置
          {
            int x = arr[j] - arr[i];
            if(hash.count(x) && x < arr[i]) 
            {
              dp[i][j] = dp[hash[x]] [i]+ 1;
              ret = max(ret, dp[i][j]);
            }
          }
          
        }
        return ret < 3 ?  0  : ret;


    }
};

最长等差数列

题目分析

代码

class Solution {
public:
    int longestArithSeqLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> hash; //放nums元素对应的下标
        hash[nums[0]] = 0;
        int ret = 2;
        vector<vector<int>> dp(n,  vector<int>(n, 2));
        for(int i = 1; i < n; i++) //固定倒数第2个数
        {
          for(int j = i + 1; j < n; j++) //依次枚举倒数第一个数
          {
              int x = 2 * nums[i]  - nums[j];
              if(hash.count(x)) dp[i][j] = dp[hash[x]][i] + 1;
              ret = max(ret,  dp[i][j]);
          }
          hash[nums[i]] = i;
        }
        return ret;
    }
};

等差数列划分 II - 子序列

题目分析

代码

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
      int n = nums.size();
      unordered_map<long long, vector<int>> hash; //存放nums元素对应的下标
      for(int i = 0; i < n; i++) hash[nums[i]].push_back(i); //每个元素的下标可能有多个

      vector<vector<int>> dp(n, vector<int>(n));
      int ret = 0;
      for(int j = 2; j < n; j++) //固定最后一个位置
      {
        for(int i = 1; i < j; i++) //依次遍历倒数第二个位置
        {
          long long x = (long long)2 * nums[i] - nums[j];
          if(hash.count(x)) 
          {
            //提取出nums[i]的下标
            for(auto k : hash[x])
            {
              if(k < i) dp[i][j] += dp[k][i] + 1;
            }
          }
          ret += dp[i][j];
         
        }
      }
      return ret;
    }
};