动态规划算法（子序列专题1）

动态规划算法专辑之子序列问题（1）

本专栏将从状态定义、状态转移方程、初始化、填表顺序、返回值这五大细节来详细讲述动态规划的算法的解题思路及代码实现

一、什么是子序列

子数列，又称子序列，在数学中，某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

下面我们将通过几道经典例题来进行讲述

二、最长递增子序列

1.题目解析

严格递增：第i个元素一定比i-1大

非严格递增：第i个元素可能比i-1大，也可能相等

要从数组中的n个子序列中，找出所有递增的子序列，并在里面找到最长的，最后返回它的长度

2.状态定义

根据经验+题目要求，我们可以得到如下定义：

dp[i]表示，以下标i元素为结尾的递增子序列的最长长度

3.状态转移方程

通过上图，我们可以发现，dp[i]有两种状态，一种是它自己就是递增子序列，一种是和前面的任意个元素组成递增子序列，对于第二种情况，我们首先要保证前面0到i-1的元素是小于nums[i]的，同时又要dp[i]是最长的长度，所以需要在0到i-1中找到最长子序列，综上，状态转移可以得到下图：

根据上图，我们可以得到如下的状态转移方程：

4.初始化

初始化也是根据题目要求+经验来进行的，并不是墨守成规的初始化为0

根据上述的状态转移方程和状态定义，我们可以将dp表里的值初始化为1，这样就对于长度为1的递增子序列，我们就不用再进行判断和计算了，使得状态只有一个了，大大简化了编码的实现

5.填表顺序

填表的顺序主要看的是状态转移方程，在方程中，dp[i]受dp[j]影响，而j又是小于i的，所以应该从左往右进行填表

6.返回值

本地不能简单的返回dp[n-1]，因为他不一定是最长的递增子序列，他只是以n-1为结尾的最长递增子序列的长度，所以我们需要遍历dp表，返回里面的最大值

7.代码实现

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        int res = 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);
                }
            }
            //填表的同时更新最大值，减少了一次for循环的遍历
            res = max(dp[i],res);
        }

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

三、最长斐波那契数列

1.题目解析

在n个子序列中，找到所有符合斐波那契数列形式的子序列，并返回最长的长度

2.状态定义

根据题目+经验，dp[i]表示：以i为结尾的斐波那契式的子序列的最长的长度

状态分析：

新的状态定义：

dp[i] [j]表示：以i及j位置为结尾的斐波那契式子序列的最长的长度（i<j）

3.状态转移方程

优化：由于数组中的元素是严格递增的，所以a的值是唯一确定的，所以a的下标也是唯一确定的，因此可以建立元素和元素下标的映射，并存入哈希表中，这样对于a的查找就大大简化了

4.初始化

根据状态定义，表里的所有值应该初始化为2，对于dp表最少有两个元素i和j

5.填表顺序

从状态转方程中看出，k<i<j,，所以应该从左到右从上到下进行填表

6.返回值

和最长递增子序列一样，应该返回的是dp表里的最大值，注意，斐波那契式的子序列的最小长度应该为3，当结果小于3时，应该返回0

7.代码实现

class Solution {
public:
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int,int> hash;
        for(int i=0;i<n;i++)
            hash[arr[i]] = i;
        vector<vector<int>> dp(n,vector<int>(n,2));
        int res = 2;
        for(int j = 2;j<n;j++)
        {
            for(int i=0;i<j;i++)
            {
                int a = arr[j] - arr[i];
                if(hash.count(a) && a < arr[i])
                {
                    int k = hash[a];
                    dp[i][j] = dp[k][i]+1;
                }
                res = max(dp[i][j],res);
            }
        }

        return res < 3 ? 0 : res;
    }
};
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
26

四、总结

本文所涉及的知识点：一维dp和二维dp，初始化的细节，状态定义（要大胆进行状态定义，错了，再改就行，当状态转移方程定义不出来的时候），返回值的细节，如何判断填表顺序

相信通过上述的两个例题，你对动态规划及子序列问题有了一定的感觉了，但对于上述问题，本文给的不一定是最优解，只是基于动态规划算法给出的解法，对于子序列问题，分析状态转移大差不差，你也可以尝试去做一些其他题练练手