【动态规划入门】最长上升子序列

一、题目描述

题目来源:LeetCode

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

输入格式
第一行包含整数 N。
第二行包含 N个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
1≤N≤1000，
−109≤数列中的数≤109

示例如下：

输入：
7
3 1 2 1 8 5 6
输出：4

 

二、思路

  按照动态规划的解题步骤，来进行分析：

1. dp[i]的定义
   dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
2. 确定状态转移方程
   位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
   所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
3. dp[i]的初始化
   每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.
4. 确定遍历顺序
   dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要把 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

 

三、C++代码

#include<bits/stdc++.h>
using namespace std;#define maxn 1010
int dp[maxn];   //dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
int nums[maxn] ; //记录整数数组 
int main(){int n;cin >> n;for(int i = 1; i <= n; i ++) {cin >> nums[i];}for(int i = 1; i <= n; i ++){dp[i] = 1;for(int j = 1; j < i; j ++){if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);}}int ans = 0;for(int i = 1; i <= n; i ++) ans = max(ans, dp[i]);cout << ans << endl;}