代码随想录:动态规划|子序列问题

300. 最长递增子序列

动态规划6部曲：

1.问题分析与转化 类比背包问题 物品：序列中的元素，背包容量：序列的长度。 求最长子序列，这个物品必须得装，如果不装，不能从当前位置转化到下一个位置。

2.dp含义：dp[i][j] 记录以nums[i]结尾最长递增子序列的长度

3.递推公式： 是找状态的转化过程！如何由上一个推导当前的状态？
对于当前位置元素 nums[i]，从i 位置前面的序列(j < i)中找到一个比它小的元素nums[j] ，然后从这个位置添加nums[i] ,之后我们可以更新长度 dp[i] = dp[j] + 1。

比如：[1, 4, 2, 3, 4, 6]
遍历过程：[1,6], [1, 4, 6], [2, 6], [2, 3, 6],[2, 3, 4, 6], 保存最长序列的长度dp[5]=4。

4.遍历顺序： 前一个状态到当前状态，自然的从前向后遍历。但内层循环也可以从后向前，为什么？根据递推公式的原理可以找到答案，我们记录的是最大值，跟顺序无关。

5.初始化 全置为1。 递推中求最大值，我们就去找最小值。最小长度递增子序列只包含自己1个元素，长度为1。

6.边界处理与优化 i可以从1开始。dp[0]包含一个元素已经初始化为1了。j < i 从i位置前边找一个数

class Solution {
 public:
  /**
   * @brief dp[i]记录以nums[i]结尾的最长递增的子序列长度（可以不连续但严格递增）
   * 然后返回dp[i]的最大值
   */
  int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    // 类比背包问题，外层是容量
    for (int i = 1; i < nums.size(); ++i) {
      // 内层扫描物品
      for (int j = 0; j < i; ++j) {
        // 如果找到比当前物品小的值，递增序列从j位置添加nums[i]元素。长度+1
        if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
      }
    }
    return *max_element(dp.begin(), dp.end());
  }
};

674. 最长连续递增子序列

思路就是：记录每一段的连续递增序列长度，然后选出最大值。

优化版本

class Solution {
 public:
  int findLengthOfLCIS(vector<int>& nums) {
    int res = 1;
    int sub = 1; ///< 连续递增序列长度
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > nums[i - 1]) {
      	//记录连续递增的长度 并更新最大值
        res = max(res, ++sub);
      } else {
      // 注意不连续的时候,从1开始计算
        sub = 1;
      }
    }
    return res;
  }
};

或者

int _findLengthOfLCIS(vector<int>& nums) {
    int res = 1;
    int sub = 1;
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] > nums[i - 1]) {
      // 连续递增序列长度
        sub++;
      } else {
      // 求最大值
        res = max(res, sub);
        sub = 1;
      }
    }
    return res;
  }