动态规划之子序列问题（上）

最长递增子序列

题目：最长递增子序列

思路

• 状态表示：dp[i]表示以i位置为结尾的所有子序列中最长递增子序列的长度

• 状态转移方程：

  • 长度为1，此时dp[i] = 1
  • 长度大于1，对于i前面的所有元素j（0 <= j < i - 1），我们考虑nums[j] < nums[i]是否成立，如果成立，则说明i位置和j位置构成递增子序列，因为不清楚是哪个j，所以我们统计其最大值dp[i] = max(dp[j] + 1, dp[i])

• 初始化：每个位置都可以构成长度为1 的递增子序列，因此将dp数组初始化为 1

• 填表顺序：从左到右

• 返回值：dp表中的最大值

C++代码

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 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;}
};

摆动序列

题目：摆动序列

思路

• 状态表示：以i位置为结尾的所有子序列中摆动序列 的 最长子序列的长度

  • f表示：以第i 个位置元素为结尾的所有的子序列中，第i 个位置呈现上升趋势的最长摆动序列的长度
  • g表示：以第i 个位置元素为结尾的所有的子序列中，第i 个位置呈现下降趋势的最长摆动序列的长度

• 状态转移方程：

  • f[i]
    • 长度为1时，f[i] = 1
    • 长度大于1，对于i前面的所有元素j（0 <= j < i - 1），我们考虑nums[j] < nums[i]是否成立，如果成立，则说明i位置和j位置构成递增子序列，则在满足这个条件下，要使j 结尾呈现下降状态，因为不清楚是哪个j，所以我们统计其最大值f[i] = max(g[j] + 1, f[i])
  • g[i]
    • 长度为1时，f[i] = 1
    • 长度大于1，对于i前面的所有元素j（0 <= j < i - 1），我们考虑nums[j] > nums[i]是否成立，如果成立，则说明i位置和j位置构成递减子序列，则在满足这个条件下，要使j 结尾呈现上升状态，因为不清楚是哪个j，所以我们统计其最大值g[i] = max(f[j] + 1, g[i])

• 初始化：每个位置都可以构成长度为1 的递增子序列，因此将f、g数组初始化为 1

• 填表顺序：从左到右两个表一起填

• 返回值：f、g表中的最大值

C++代码

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[i] > nums[j]){f[i] = max(g[j] + 1, f[i]);}else if(nums[j] > nums[i]) {g[i] = max(f[j] + 1, g[i]);}}ret = max(ret, max(f[i], g[i]));}return ret;}
};

最长递增子序列的个数

题目：最长递增子序列的个数

思路

• 状态表示：

  • len[i]表示以i位置为结尾的所有子序列中最长递增子序列的长度
  • count[i]表示以i位置为结尾的所有子序列中最长递增子序列的个数

• 状态转移方程：

  • len[i]
    • 长度为1，此时len[i]= 1
    • 长度大于1，对于i前面的所有元素j（0 <= j < i - 1），我们考虑nums[j] < nums[i]是否成立，如果成立，则说明i位置和j位置构成递增子序列，因为不清楚是哪个j，所以我们统计其最大值len[i] = max(len[j] + 1, len[i])
  • count[i] ，使用 j表示 [0, i - 1] 区间上的下标
    • 当nums[j] < nums[i]时，如果len[j] + 1 == len[i]，此时count[i] += count[j]
    • 当nums[j] < nums[i]时，如果len[j] + 1 < len[i]，此时无视
    • 当nums[j] < nums[i]时，如果len[j] + 1 > len[i]，此时更新len[i] = len[j] + 1, count[i] = count[j]

• 初始化：

  • len[i]，每个位置都可以构成长度为1 的递增子序列，因此将len数组初始化为 1
  • count[i]，初始化为 1

• 填表顺序：从左到右两个表一起填

• 返回值：最长递增子序列的个数

C++代码

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

最长数对链

题目：最长数对链

思路

• 排序： 首先，对数对数组按照每个数对的第一个元素进行升序排序。这是为了方便后续动态规划的处理

• 状态表达： dp[i] 表示以第i 个数对为结尾的所有数对链，最长数对链的长度

• 状态转移方程：

  • 长度为1，此时1
  • 长度大于1， 对于i前面的所有元素j（0 <= j < i - 1），若有p[j][1] < p[i][0]，则说明i位置和j位置构成递增数对链，因为不清楚是哪个j，所以我们取其最大值dp[i] = max(dp[j] + 1, dp[i])，其中 0 <= j < i

• 初始化： 全部初始化为1

• 填表顺序： 从左往右

• 返回值： 根据状态表达，返回整个 dp数组中的最大值

C++代码

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