【动态规划】求最长递增子序列问题

这篇具有很好参考价值的文章主要介绍了【动态规划】求最长递增子序列问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述

最长递增子序列(Longest Increasing Subsequence,LIS

  • 子序列:对于任意序列s,它的子序列是通过删除其中零个或多个元素得到的另⼀个序列
    注:剩余元素的相对顺序保持不变

给定n个整数组成的序列 s [ 1... n ] s[1...n] s[1...n],求最长递增子序列LIS(的长度)

8 3 6 1 3 5 4 7

递推关系

建立递推关系的思路

假设能够求出 s [ 1... k − 1 ] s[1...k-1] s[1...k1]LIS,考虑能否由此推出 s [ 1... k ] s[1...k] s[1...k]LIS

  • 如果仅知道长度
    • 无法判断 s [ k ] s[k] s[k] 能否让LIS变长
  • 如果不仅知道长度,还知道具体序列 L
    • s [ k ] s[k] s[k] 能让 L 变长,那问题就解决了
    • 也许 L 就是 s [ 1... k ] s[1...k] s[1...k]LIS
    • 也许存在 s [ 1... k ] s[1...k] s[1...k] 的另⼀个LIS:L‘, s [ k ] s[k] s[k] 能让L’变长
    • 可能需要记住 s [ 1... k − 1 ] s[1...k-1] s[1...k1] 的所有LIS

原始子问题: 令 L ( k ) L(k) L(k) 表示 s [ 1... k ] s[1...k] s[1...k]LIS的长度,原问题即求解 L ( n ) L(n) L(n)

  • O(n)个子问题,但不容易建立递归关系

约束条件:以 s [ k ] s[k] s[k] 结尾

  • L ( k ) L(k) L(k) 表示 s [ 1... n ] s[1...n] s[1...n] s [ k ] s[k] s[k] 结尾LIS的长度
  • 原问题即为求解 max ⁡ 1 ≤ k ≤ n L ( k ) \max_{1\le k\le n}L(k) max1knL(k)
  • 基本情况: 如果 k = 1 k = 1 k=1,那么 L ( k ) = 1 L(k) = 1 L(k)=1
  • 归纳步骤
    • L k = max ⁡ { 1 , max ⁡ 1 ≤ i ≤ k − 1 { L ( i ) + 1 ∣ s [ k ] > s [ i ] } } L_k = \max \{1, \max_{1\le i \le k-1} \{ L(i) +1 | s[k] > s[i] \}\} Lk=max{1,max1ik1{L(i)+1∣s[k]>s[i]}},其中, max ⁡ ⊘ \max \oslash max的值定义为0

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下

  • 此时的递推关系:

L ( k ) = { 1 i f k = 1 max ⁡ { 1 , max ⁡ 1 ≤ i ≤ k − 1 { L ( i ) + 1 ∣ s [ k ] > s [ i ] } } i f k > 1 L(k) = \begin{cases} 1 &if\quad k=1\\ \max \{1, \max_{1\le i \le k-1} \{ L(i) +1 | s[k] > s[i] \}\} &if \quad k>1 \end{cases} L(k)={1max{1,max1ik1{L(i)+1∣s[k]>s[i]}}ifk=1ifk>1

  • O ( n ) O(n) O(n) 个子问题,每个子问题复杂度为 O ( k ) O(k) O(k)。时间复杂度为 O ( n 2 ) O(n^2) O(n2)

约束条件:以 s [ k ] s[k] s[k] 开头

  • L ( k ) L(k) L(k) 表示 s [ 1... n ] s[1...n] s[1...n] s [ k ] s[k] s[k] 开头LIS的长度
  • 原问题即为求解 max ⁡ 1 ≤ k ≤ n L ( k ) \max_{1\le k\le n}L(k) max1knL(k)
  • 基本情况: 如果 k = n k = n k=n,那么 L ( k ) = 1 L(k) = 1 L(k)=1

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下

  • 此时的递推关系:

L ( k ) = { 1 i f k = n max ⁡ { 1 , max ⁡ k + 1 ≤ i ≤ n { L ( i ) + 1 ∣ s [ k ] < s [ i ] } } i f k < n L(k) = \begin{cases} 1 &if\quad k=n\\ \max \{1, \max_{k+1\le i \le n} \{ L(i) +1 | s[k] < s[i] \}\} &if \quad k<n \end{cases} L(k)={1max{1,maxk+1in{L(i)+1∣s[k]<s[i]}}ifk=nifk<n

  • O ( n ) O(n) O(n) 个子问题,每个子问题复杂度为 O ( k ) O(k) O(k)。时间复杂度为 O ( n 2 ) O(n^2) O(n2)

约束条件:增加子问题参数(前缀)

  • L ( i , j ) L(i,j) L(i,j) 表示 s [ j . . . n ] s[j...n] s[j...n] 中每个元素都大于 s [ i ] s[i] s[i] LIS的长度
  • s [ 0 ] = − ∞ s[0] =-\infty s[0]= ,原问题即求解 L ( 0 , 1 ) L(0,1) L(0,1)
  • 基本情况: 如果 j > n j> n j>n ,那么 L ( i , j ) = 0 L(i,j)= 0 L(i,j)=0

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下

  • 归纳步骤
    • 如果 s [ i ] > s [ j ] s[i] > s[j] s[i]>s[j] L ( i , j ) = L ( i , j + 1 ) L(i,j) = L(i,j+ 1) L(i,j)=L(i,j+1)
    • 否则 L ( i , j ) = max ⁡ { L ( i , j + 1 ) , 1 + L ( j , j + 1 ) } L(i,j) = \max \{ L(i,j+ 1),1 + L(j,j+ 1)\} L(i,j)=max{L(i,j+1),1+L(j,j+1)}
  • O ( n 2 ) O(n^2) O(n2)个子问题,每个子问题求解复杂度为 O ( 1 ) O(1) O(1),时间复杂度: O(n2); 空间复杂度: O(n2)
  • 此时的递推关系:
    L ( i , j ) = { 0 i f j > n L ( i , j + 1 ) i f s [ i ] ≥ s [ j ] max ⁡ { L ( i , j + 1 ) 1 + L ( j , j + 1 ) o t h e r w i s e L(i,j) = \begin{cases} 0 &if\quad j>n\\ L(i,j+1) &if\quad s[i]\ge s[j] \\ \max \begin{cases} L(i,j+1) \\ 1+L(j,j+1) \end{cases} &otherwise \end{cases} L(i,j)= 0L(i,j+1)max{L(i,j+1)1+L(j,j+1)ifj>nifs[i]s[j]otherwise

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下


约束条件:增加子问题参数(后缀)

  • L ( i , j ) L(i,j) L(i,j) 表示 s [ 1... j ] s[1...j] s[1...j] 中每个元素都小于 s [ i ] s[i] s[i] LIS的长度
  • s [ n + 1 ] = ∞ s[n+1] =\infty s[n+1]= ,原问题即求解 L ( n + 1 , n ) L(n+1,n) L(n+1,n)
  • 基本情况: 如果 j = 0 j=0 j=0 ,那么 L ( i , j ) = 0 L(i,j)= 0 L(i,j)=0

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下

  • 归纳步骤

    • 如果 s [ i ] ≤ s [ j ] s[i] \le s[j] s[i]s[j] L ( i , j ) = L ( i , j − 1 ) L(i,j) = L(i,j- 1) L(i,j)=L(i,j1)
    • 否则 L ( i , j ) = max ⁡ { L ( i , j − 1 ) , 1 + L ( j , j − 1 ) } L(i,j) = \max \{ L(i,j- 1),1 + L(j,j- 1)\} L(i,j)=max{L(i,j1),1+L(j,j1)}
  • 此时的递推关系:
    L ( i , j ) = { 0 i f j = 0 L ( i , j − 1 ) i f s [ i ] ≤ s [ j ] max ⁡ { L ( i , j − 1 ) 1 + L ( j , j − 1 ) o t h e r w i s e L(i,j) = \begin{cases} 0 &if\quad j=0\\ L(i,j-1) &if\quad s[i]\le s[j] \\ \max \begin{cases} L(i,j-1) \\ 1+L(j,j-1) \end{cases} &otherwise \end{cases} L(i,j)= 0L(i,j1)max{L(i,j1)1+L(j,j1)ifj=0ifs[i]s[j]otherwise

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下


约束条件:LIS长度为k且末尾元素最小

  • 对于长度为 k k k 的递增子序列,只需记住末尾元素最小的那个

  • 本质是寻找上限最高(可拓展性最强)的那个子序列

  • L ( k ) L(k) L(k) 表示 s [ 1... n ] s[1...n] s[1...n] 中长度为 k k k 且末尾元素最小的递增子序列,且 L ( k ) . l a s t L(k).last L(k).last 表示该序列中最后那个元素

  • 引理: L ( 1 ) . l a s t < L ( 2 ) . l a s t < . . . < L ( k ) . l a s t L(1) .last < L(2) .last < ... < L(k).last L(1).last<L(2).last<...<L(k).last

    • 假设 x ≥ y x \ge y xy,而 y ≥ z y \ge z yz,所以 x ≥ z x \ge z xz
    • 那么灰色元素构成一个长度为 k k k 且末尾元素最小的递增子序列,矛盾
      6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下
  • 归纳假设: 对长度小于 n n n 的序列,可以计算其所有的 L ( k ) L(k) L(k),并有序存储

  • 基本情况: 长度为1的序列,有 L [ 1 ] ← s [ 1 ] L[1]\leftarrow s[1] L[1]s[1]

  • 如何基于归纳假设求解 s [ 1.. n ] s[1..n] s[1..n] 的所有的 L ( k ) L(k) L(k)

    • L ( k ) . l a s t L(k).last L(k).last 构成的有序数组中查找插入位置 k ′ k' k,使得 s [ n ] s[n] s[n] 加入后仍然有序
    • 如果 k ′ = k + 1 k' =k+1 k=k+1,那么 L ( k + 1 ) + L ( k ) + 1 L(k + 1) + L(k) +1 L(k+1)+L(k)+1 L ( k + 1 ) . l a s t ← s [ n ] L(k + 1).last \leftarrow s[n] L(k+1).lasts[n]
    • 否则 L ( k ′ ) . l a s t ← s [ n ] L(k').last \leftarrow s[n] L(k).lasts[n],但 L ( k ′ ) L(k') L(k) 的值不变
  • 时间复杂度: O ( l o g n ) O(logn) O(logn)

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下


运行实例

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

ostream& operator<<(ostream& os, const vector<int>& v) {
    for (auto e : v)
        os << e << ' ';
    return os;
}

int lis_dp1(const vector<int>& s, int n) {
    vector<int> dp(n + 1, 1); // 初始化dp数组,dp[i]表示以s[i]结尾的LIS的长度

    for (int k = 2; k <= n; ++k) {
        for (int i = 1; i < k; ++i) {
            if (s[k] > s[i]) {
                dp[k] = max(dp[k], dp[i] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end()); // 返回dp数组中的最大值作为整个序列的最长递增子序列的长度
}

int lis_dp2(const vector<int>& s, int n) {
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, -1)); // 初始化dp数组,dp[i][j]表示L(i,j)

    for (int i = 0; i <= n + 1; ++i)
        dp[i][n + 1] = 0; // 基本情况:当 j > n 时,L(i,j) = 0

    for (int j = n; j >= 1; --j) {
        for (int i = 0; i < j; ++i) {
            if (s[i] >= s[j]) {
                dp[i][j] = dp[i][j + 1]; // 如果s[i] >= s[j],则L(i,j) = L(i,j+1)
            }
            else {
                dp[i][j] = max(dp[i][j + 1], 1 + dp[j][j + 1]); // 否则L(i,j) = max{L(i,j+1), 1+L(j,j+1)}
            }
        }
    }

    return dp[0][1]; // 返回L(0,1)作为整个序列的最长递增子序列的长度
}

int lis_dp3(const vector<int>& s, int n) {
    
    if (n == 0) return 0;

    set<int> L;

    L.insert(s[1]);

    for (int i = 2; i < n+1; ++i) {
        if (s[i] > * L.rbegin()) {
            L.insert(s[i]);
        }
        else {
            L.erase(L.lower_bound(s[i]));
            L.insert(s[i]);
        }
    }

    return L.size();
}

vector<int> find_lis_dp1(const vector<int>& s, int n) {
    vector<int> dp(n + 1, 1); // 初始化dp数组,dp[i]表示以s[i]结尾的LIS的长度
    vector<int> parent(n + 1, -1); // 记录每个元素的父节点索引

    for (int k = 2; k <= n; ++k) {
        for (int i = 1; i < k; ++i) {
            if (s[k] > s[i] && dp[k] < dp[i] + 1) {
                dp[k] = dp[i] + 1;
                parent[k] = i; // 更新父节点索引
            }
        }
    }

    int max_length = *max_element(dp.begin(), dp.end()); // 获取最长递增子序列的长度
    int max_index = distance(dp.begin(), find(dp.begin(), dp.end(), max_length)); // 获取最长递增子序列的结束索引

    vector<int> lis;
    while (max_index != -1) {
        lis.push_back(s[max_index]);
        max_index = parent[max_index]; // 根据父节点索引回溯
    }

    reverse(lis.begin(), lis.end()); // 反转得到正确顺序的最长递增子序列

    return lis;
}

vector<int> find_lis_dp2(const vector<int>& s, int n) {
    vector<vector<int>> dp(n + 2, vector<int>(n + 2, -1)); // 初始化dp数组,dp[i][j]表示L(i,j)
    vector<vector<int>> parent(n + 2, vector<int>(n + 2, -1)); // 记录每个元素的父节点索引

    for (int i = 0; i <= n + 1; ++i)
        dp[i][n + 1] = 0; // 基本情况:当 j > n 时,L(i,j) = 0

    for (int j = n; j >= 1; --j) {
        for (int i = 0; i < j; ++i) {
            if (s[i] >= s[j]) {
                dp[i][j] = dp[i][j + 1];
            }
            else {
                dp[i][j] = max(dp[i][j + 1], 1 + dp[j][j + 1]);
                if (dp[i][j] == dp[j][j + 1] + 1) {
                    parent[i][j] = j; // 更新父节点索引
                }
            }
        }
    }

    vector<int> lis;
    int i = 0, j = 1;
    while (j <= n) {
        if (dp[i][j] == dp[j][j + 1] + 1) {
            lis.push_back(s[j]);
            i = j;
        }
        ++j;
    }

    return lis;
}

vector<int> find_lis_dp3(const vector<int>& s, int n) {
    vector<int> lis;
    set<int> L;

    L.insert(s[1]);

    for (int i = 2; i < n + 1; ++i) {
        if (s[i] > *L.rbegin()) {
            L.insert(s[i]);
        }
        else {
            L.erase(L.lower_bound(s[i]));
            L.insert(s[i]);
        }
    }
    
    for (int num : L) {
        lis.push_back(num);
    }
    return lis;
}

int main(int argc, const char* argv[]) {
    vector<int> s = { -1, 8, 3, 6, 1, 3, 5, 4, 7 }; // 注意s[0]仅作标识,真实数据为s[1]~s[n]
    cout << lis_dp1(s, s.size() - 1) << endl;
    cout << find_lis_dp1(s, s.size() - 1) << endl;
    cout << "------------------------------"  << endl;
    cout << lis_dp2(s, s.size() - 1) << endl;
    cout << find_lis_dp2(s, s.size() - 1) << endl;
    cout << "------------------------------" << endl;
    cout << lis_dp3(s, s.size() - 1) << endl;
    cout << find_lis_dp3(s, s.size() - 1) << endl;
    cout << "------------------------------" << endl;
    return 0;
}

运行结果:

6-8 求解最长递增子序列问题(动态规划法) 分数 10 全屏浏览题目 切换布局 作者 王,算法学习,算法,动态规划,LIS,最长递增子序列,约束条件,自底向上,自顶向下文章来源地址https://www.toymoban.com/news/detail-774574.html


到了这里,关于【动态规划】求最长递增子序列问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 矩阵链相乘(动态规划法)

    矩阵链乘法是耳熟能详的问题了,有很多矩阵,排列成矩阵链,矩阵链的要求是相邻的两个是可以相乘的,可以相乘是有条件的,两个矩阵能够相乘的条件就是行、列之间是有关系的,两个矩阵如果能够相乘,就是前面矩阵的列号和后面矩阵的行号是一致的。 如何确定矩阵的

    2024年02月09日
    浏览(50)
  • 南邮|算法分析与设计实验二 动态规划法

    目录 实验目的 实验内容 实验步骤 一、最长公共子序列 二、矩阵连乘  加深对动态规划法的算法原理及实现过程的理解,学习用动态规划法解决实际应用中的 最长公共子序列问题 和 矩阵连乘问题 ,体会 动态规划法 和 备忘录方法 的异同。 一、用动态规划法和备忘录方法

    2024年02月01日
    浏览(45)
  • C++每日一练:打家劫室(详解动态规划法)

    这题目出得很有意思哈,打劫也是很有技术含量滴!不会点算法打劫这么粗暴的工作都干不好。 提示:以下是本篇文章正文内容,下面案例可供参考 题目名称: 打家劫舍 题目描述: 一个小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素

    2024年02月02日
    浏览(46)
  • 动态规划算法 | 最长递增子序列

    通过查阅相关资料 发现动态规划问题一般就是求解最值问题 。这种方法在解决一些问题时应用比较多,比如求最长递增子序列等。 有部分人认为动态规划的核心就是:穷举。因为要求最值,肯定要把所有可行的答案穷举出来,然后在其中找最值。 首先,笔者认为动态规划中

    2024年02月06日
    浏览(54)
  • 动态规划之最长递增子序列

    leetcode 300 最长递增子序列 1.定义dp数组:dp[i]表示以nums[i]结尾的最长递增子序列的长度。 2.定义递推公式 dp[i] = max(dp[j] + 1, dp[i]) 因为dp[j] + 1中的dp[j]并非是在前一个已经加1的dp[j]的基础之上再加上1。若从初始状态加1,而dp[i]永远保持的是最大的状态,则dp[j] + 1肯定要小一些。

    2024年01月23日
    浏览(46)
  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(48)
  • 力扣--动态规划300.最长递增子序列

    一开始想到的方法非常低效,但好理解。   思路分析: 使用二维数组 dp 来记录递增子序列的长度信息,其中 dp[i][0] 表示以 nums[i] 结尾的最长递增子序列的长度, dp[i][1] 表示包含 nums[i] 的最长递增子序列的长度。 初始化 dp 数组,将以第一个元素结尾的递增子序列长度置为

    2024年01月24日
    浏览(49)
  • 动态规划9:最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列、不相交的线、最长子序和

    例题300: 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 确定dp数组和下标含义 dp[i]表示在第i个元素的最长子序列数

    2024年04月08日
    浏览(44)
  • 最优控制理论 九、Bellman动态规划法用于最优控制

    尽管DP也是最优控制理论的三大基石之一,但长久以来,动态规划法(Dynamic Programming)被认为只能在较少控制变量的多阶段决策问题中使用,维数灾难使他不可能搜索得了整个连续最优控制问题的高维状态空间,因此仍然只能在一些维数较低的离散决策变量最优选择中取得较好

    2024年02月01日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包