动态规划之线性dp(下)

一、 最长上升子序列(一)

描述
给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 i和 j 满足 i<j且 arri≥arrj。
数据范围：0≤n≤1000 ,|arri∣≤10 ^9

要求：时间复杂度 O(n^2)， 空间复杂度 O(n)
输入描述：
第一行输入一个正整数 n ，表示数组的长度
第二行输入 n 个整数表示数组的每个元素。
输出描述：
输出最长严格上升子序列的长度
示例1
输入：
7
6 3 1 5 2 3 7
复制
输出：
4
复制
说明：
该数组最长上升子序列为 [1,2,3,7] ，长度为4

解法:

这是一道动态规划题目。将其分解为子问题，即分解成求解n个 以0到n-1下标的数为结尾的子序列的最大长度的问题。
可以用一个dp数组保存每个数做结尾时对应的最大长度。
假设一个以第i个元素arr[i]结尾的子序列Si，那么Si的长度是由i在Si中的前一个元素arr[j]决定的，Si的长度就等于Sj的长度加一。

这前面一个数arr[j]必须要满足两个条件：

arr[j]<arr[i],这样才能构成严格上升
dp[j]的值在i之前的所有dp中最大，这样我们求的才是最大长度。

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

int main(){
    
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vector<int> dp(n,1);//以i下标的数为结尾的子序列的长度
    
    for(int i=1;i<n;i++){
    
        int mx=0;
        for(int j=0;j<i;j++){
    
            //每一个元素的dp值==在它之前的，比它小的元素中最大的dp值加一
            if(arr[i]>arr[j])
                mx=max(mx,dp[j]);
        }
        dp[i]=mx+1;
    }
    int res=1;
    for(int i=0;i<n;i++)
        res=max(res,dp[i]);
    cout<<res;
    return 0;
}

时间复杂度：O(n^2)
空间复杂度：O(n)

二、最长公共子序列(一)

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
    
    
public:
    int longestSeqNum(string &s, string &t){
    
        int m = s.size();
        int n = t.size();
        vector<vector<uint64_t>>dp(m+1,vector<uint64_t>(n+1,0));// dp[i][j] 表示 i-1结尾的s j-1结尾 t的
        // 最长公共 子序列的长度
        // 注意要弄懂 dp[i][j] 的含义 不要有 dp[0][0] = 1; 这什么鬼
        for (int i =1;i<=m;i++){
    
            for(int j =1;j<= n;j++){
    
                
                if(s[i-1] ==t[j-1]){
    
                    dp[i][j] = dp[i-1][j-1] +1;
                }else {
    
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
        
    }
    
};

int main(){
    
    
    int n,m;
    string s,t;
    // 题目输入格式
    cin >> n >> m;
    cin >> s>> t;
    
    Solution solu;
    cout<< solu.longestSeqNum(s,t) <<endl;
    
    
    return 0;
}