[Algorithm][动态规划][子序列问题][最长递增子序列][摆动序列]详细讲解

---

0.子序列 vs 子数组

• 子序列：
  • 相对顺序是跟源字符串/数组是一致的
  • 但是元素和元素之间，在源字符串/数组中可以是不连续的
  • 一般时间复杂度：$O(2^n)$
• 子数组：
  • 在源字符串/数组中挑出来，必须是连续的
    • 子串与子数组是一个意思
  • 一般时间复杂度：$O(N^2)$
• 子序列其实相当于包含了子数组
• 子序列问题经典解法：两层循环

---

1.最长递增子序列

1.题目链接

• 最长递增子序列

---

2.算法原理详解

• 注意：本题思考方式非常有标志性
• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 以i位置元素为结尾的所有子序列中，最长递增子序列的长度

  • 推导状态转移方程
    

  • 初始化：vector<int> dp(n, 1)

  • 确定填表顺序：从左往右

  • 确定返回值：整个dp表里的最大值

---

3.代码实现

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 j = 0; j < i; j++)
        {
            if(nums[j] < nums[i])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }

        ret = max(ret, dp[i]);
    }

    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

2.摆动序列

1.题目链接

• 摆动序列

---

2.题目链接

• 思路：

  • 确定状态表示 -> dp[i]的含义

    • 以i位置元素为结尾的所有子序列中，最长的摆动序列的长度
    • 本题状态标识还可以继续划分
      • f[i]：以i位置元素为结尾的所有子序列中，最后一个位置呈现“上升”趋势的最长的摆动序列的长度
      • g[i]：以i位置元素为结尾的所有子序列中，最后一个位置呈现“下降”趋势的最长的摆动序列的长度

  • 推导状态转移方程

    • 令j为i前面的任一一个数
      

  • 初始化：vector<int> f(n, 1), g(n, 1)

  • 确定填表顺序：从左往右，两个表一起填

  • 确定返回值：两个dp表里的最大值

---

3.代码实现

int wiggleMaxLength(vector<int>& nums) 
{
    int n = nums.size();
    vector<int> f(n, 1), 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(ret, max(f[i], g[i]));
    }

    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25