最长单调递增子序列问题的动态规划算法时间复杂度

最长单调递增子序列问题的动态规划算法时间复杂度为$O(n^2)$。具体来说，算法的主要步骤包括：

1. 初始化一个长度为n的数组dp，其中dp[i]表示以第i个元素为结尾的最长递增子序列的长度。

2. 遍历数组中的每个元素i，对于每个元素i，内部再遍历该元素前面的所有元素j(0<=j<i)，如果j比i小且a[j]<a[i]，则更新dp[i]的值为dp[j]+1。

3. 遍历完整个数组后，dp数组中的最大值即为最长递增子序列的长度。

在这个算法中，每个元素需要遍历其前面的所有元素，时间复杂度为$O(n^2)$。

相关问题

最长单调递增子序列问题和数字三角形问题的动态规划算法实现和效率分析

最长单调递增子序列问题的动态规划算法实现：

1. 定义状态：dp[i]表示以第i个元素为结尾的最长单调递增子序列的长度。

2. 初始化：dp[i]初始值为1，因为任意一个元素本身就是一个长度为1的单调递增子序列。

3. 状态转移方程：对于每个元素i，枚举其之前的元素j（j<i），如果nums[j] < nums[i]，则dp[i] = max(dp[i], dp[j]+1)。

4. 最终结果：遍历dp数组，找到最大值。

代码实现：

def longestIncreasingSubsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

数字三角形问题的动态规划算法实现：

1. 定义状态：dp[i][j]表示从顶部走到(i,j)位置的最小路径和。

2. 初始化：dp[0][0] = triangle[0][0]，其他dp[i][j]的初始值为正无穷。

3. 状态转移方程：对于每个位置(i,j)，有两个状态可以转移过来，即(i-1,j)和(i-1,j-1)，因此dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]。

4. 最终结果：遍历dp数组的最后一行，找到最小值。

代码实现：

def minimumTotal(triangle):
    n = len(triangle)
    dp = [[float('inf')] * n for _ in range(n)]
    dp[0][0] = triangle[0][0]
    for i in range(1, n):
        for j in range(i+1):
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]
    return min(dp[-1])

效率分析：

最长单调递增子序列问题的时间复杂度为O(n^2)，空间复杂度为O(n)。

数字三角形问题的时间复杂度为O(n^2)，空间复杂度为O(n^2)。

P1309 最长单调递增子序列

题目描述

给出一个长度为n的序列，请找出最长的不下降子序列。（若有多个答案，请输出其中字典序最小的）。

输入格式

第一行包含整数n。

第二行包含n个整数，表示整个序列。

输出格式

第一行包含整数m，表示最长不下降子序列的长度。

第二行包含m个整数，表示最长不下降子序列。

数据范围

1≤n≤1000，1≤序列中的数≤10000

输入样例：

5
3 1 4 2 5

输出样例：

3
3 4 5

算法

(动态规划) $O(n^2)$

时间复杂度

状态数O(n),状态转移O(n),总时间复杂度O(n^2)

空间复杂度

O(n)

C++ 代码

class Solution {
public:
vector<int> LIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
vector<vector<int>> path(nums.size());
dp[0] = 1;
path[0].push_back(nums[0]);
int max_length = 1, max_pos = 0;
for (int i = 1; i < nums.size(); i++) {
int max_dp = 1, max_j = -1;
for (int j = 0; j < i; j++) {
if (nums[j] <= nums[i] && dp[j] + 1 > max_dp) {
max_dp = dp[j] + 1;
max_j = j;
}
}
dp[i] = max_dp;
if (max_j != -1) {
path[i] = path[max_j];
}
path[i].push_back(nums[i]);
if (dp[i] > max_length) {
max_length = dp[i];
max_pos = i;
}
}
return path[max_pos];
}
};