DP专题 | LIS POJ - 2533

POJ - 2533 Longest Ordered Subsequence

Description

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK<= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

Input

The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000

Output

Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

```7
1 7 3 5 9 4 8```

Sample Output

`4`

LIS是典型的DP题，dp[i]表示以数字a[i]结尾的最长子序列的最大长度，从位置1一直到N，显然可以采用递推的方式解决。

LIS的转移方程不那么直观，上一篇数字三角形中dp[i]的计算会依赖dp[i-1]，这也是很多时候会用到的模式，而LIS需要一个循环才能算出dp[i]，依赖dp[j(0<j<i)]。说明dp在转移时可能形式多样，dp[i]肯定依赖i之前的dp，但是没有定式，逻辑可能比较复杂，也因此使得DP算法灵活多变。

LIS除了计算最大长度，有时候可能需要记录最长序列的值，采用一个表记录即可，path[i]=j表示i的前驱节点是j，其实对于每一个节点，在更新的过程中只可能有一个前驱节点，因此是不会存在问题的。

```#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <set>
#include <limits.h>
#include <vector>
#include <string>
#include <bitset>
using namespace std;

#ifdef __APPLE__
#define printfd printf
#else
#define printfd
#endif

#define MAX_SIZE 1000000

int main()
{
#ifdef __APPLE__
freopen("test.txt", "r", stdin);
#endif
int n;
scanf("%d", &n);

vector<int> v(n+1, 0);
for(int i=1; i<=n; ++i){
scanf("%d", &v[i]);
}

int dp[MAX_SIZE] = {0};
int path[MAX_SIZE] = {0};
int max = 0;
int pos = 0;

for(int i=1; i<=n; ++i){
//dp[i] = max(0,dp[j]) + 1
int m = 0;
for(int j=1; j<i; ++j){
if(v[j] < v[i]){
if(dp[j] > m){
path[i] = j;
//printfd("j->i %d->%d\n", j, i);
}
m = std::max(m, dp[j]);
}
}
dp[i] = m + 1;
if(dp[i] > max){
pos = i;
}
max = std::max(dp[i], max);
printfd("dp[%d]=%d\n", i, dp[i]);
}

printf("%d\n", max);
while(pos > 0){
printfd("%d ", pos);
pos = path[pos];
}
printfd("\n");

return 0;
}```

0 条评论

• 最长上升子序列（LIS）算法

LIS（Longest Increasing Subsequence）最长上升子序列 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列...

• 字符串的距离(动态规划) - leetcode 72

，因为在刷leetcode的动态规划专题。动态规划虽然定义很简单，但是对于复杂的动态规划题目，很多时候还是很棘手的。

• 石子合并（区间动态规划）- NYOJ 737

有N堆石子排成一排，每堆石子有一定的数量。现要将N堆石子并成为一堆。合并的过程只能每次将相邻的两堆石子堆成一堆，每次合并花费的代价为这两堆石子的...

• Leetcode 70 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time...

• 穿上衣服我就不认识你了？来聊聊最长上升子序列

最长上升子序列是一个很经典的算法题。有的会直接让你求最长上升子序列，有的则会换个说法，但最终考察的还是最长上升子序列。那么问题来了，它穿上衣服你还看得出来是么？

• 【POJ 2250】Compromise(最长公共子序列LCS)

题目 字符串的LCS，输出解我比较不会，dp的时候记录从哪里转移来的，之后要一步一步转移回去把解存起来然后输出。

• LintCode 最长公共子序列题目分析代码

典型的动态规划问题 dp[i][[j]：表示前i个和前j个字符最大LCS 当A[i] = B[i]的时候： 那么显然dp[i][j] = dp[i-1][...

• 画解算法：70. 爬楼梯

https://leetcode-cn.com/problems/climbing-stairs/