3最长递增子序列(附带动态规划知识点讲解)｜刷题打卡

发表于

一、题目描述：


二、思路分析：

这是一道很简单的动态规划，在这里讲解下动态规划的一般思路
动态规划算法能解决的问题有以下几种特征：

  1. 具有相同子问题：首先我们必须要保证这个问题能够分解出几个子问题，并且能够通过这些子问题来解决这个问题
  2. 满足最优化原理（最优子结构）：问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。
  3. 具有无后效性：每个子问题的决策，不能够对解决其他未来的问题产生影响稍后会解释本题如何消除后效性

解题步骤

第一步：确定问题的子问题 ，要点：注意分析哪些量随着问题规模的变小是会变小的，哪些变量与问题无关。

第二步：确定状态， 要点：结合子问题，敢想敢试，不要轻易否定一个状态，多思考，不要希望每个题都能一蹴而就！

第三步：推出状态转移方程 要点：注意验证适用条件是否满足，注意不要漏掉条件。

第四步：确定边界条件 要点：先根据状态含义确定，确定后验证第一层是否正确，如果不正确或
者无法按含义确定，则也可以采用第一层的值反推的方式确定边界。

第五步：确定实现方式 要点：根据拓扑序是否明显和个人习惯确定！

第六步：如果需要的话，确定优化方法！ 要点：注意优先考虑能否降维，不要局限于单调队列，四边形不等式这些标准的用于譤議优化的东西，扩宽思维，避免定式！

实践出真知

第一步：在这道题中，问题规模无疑是数组最大长度（你可以理解为右指针），而随着最大长度减小，递增子序列的长度也会减小。但是！长度也可能不变，因为最大长度减小时排除的那个数，未必包含在当前的最长递增子序列中。

第二步：之前说到后效性问题，很明显，是否选择了第i个点，作为递增子序列的一部分，这对后面的答案一定是有影响的，因此我们设置状态为dp[i][0]为长度为i时，不选择第i个点加入递增子序列的长度，dp[i][1]为长度为i时，选择第i个点加入递增子序列的长度。

第三步：推出状态转移方程，不选择第i个点加入递增子序列时，最大长度就相当于dp[i - 1][*]的最大值，而选择第i个点加入递增子序列时，最大长度相当于一个dp[过去的点]+1，而这个点的值必须严格小于第i个点。当然如果没有点满足要求，则将其设置为1。具体如下

1
2
3
C++复制代码dp[i][0] = max(dp[i - 1][0] , dp[i - 1][1]);
dp[i][1] = 1;
if(nums[j] < nums[i])dp[i][1] = max(dp[j][1] + 1, dp[i][1]);

第四步: 边界条件，方程需要根据前面的节点而得到答案，因此i == 0时，是步具备前面的节点的，需要单独指定

第五步：实现方式略

第六步：优化略

三、AC 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
C++复制代码class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[nums.size()][2];
        dp[0][0] = 0;
        dp[0][1] = 1;
        for(int i = 1 ; i < nums.size(); i++){
            
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
            int j = i - 1;
            dp[i][1] = 1;
            while(j >= 0){
                if(nums[j] < nums[i])dp[i][1] = max(dp[j][1] + 1, dp[i][1]);
                j--;
            }
            // printf("%d:%d ", dp[i][0],dp[i][1]);
        }

        return max(dp[nums.size() - 1][0] , dp[nums.size() - 1][1]);
    
    }
};

四、总结：

这道题在不难的同时，需要自己去消除无后效性的影响，我觉得有作为一道例题讲的价值。
接下来我去再看看动态规划的知识，学成以后继续发这个系列。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%