前言
今天我们继续讨论经典的动态规划问题之最长上升子序列问题。
最长上升子序列问题
问题描述
给定一个数字序列A，求该序列中最长上升子序列的长度。例如A={1,4,2,5,3}，其最长上升子序列为{1,2,3}，因此最长上升子序列的长度为3。
问题分析
假设序列长度为
，构建一个长度为
的一维数组
，
代表了以
结尾的上升子序列的长度。很显然，
，最长上升子序列的长度为
。
代码实现
通过问题分析，可以很容易得用代码实现，下面给出算法的java实现。
public class LongestIncreasingSubsequence {
public int getLIS(int[] A, int n) {
return core(A, n);
}
// 动态规划
public static int core(int[] A, int n) {
if (n == 0) {
return 0;
}
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i++) {
int max = 0;
for (int j = 0; j < i; j++) {
if (A[i] > A[j]) {
max = Math.max(max, dp[j]);
}
}
dp[i] = max + 1;
}
int res = 0;
for (int i = 0; i < n; i++) {
if (res < dp[i]) {
res = dp[i];
}
}
return res;
}
public static void main(String[] args) {
LongestIncreasingSubsequence main = new LongestIncreasingSubsequence();
int[] A = new int[]{1, 4, 2, 5, 3};
int n = 5;
System.out.println(main.getLIS(A, n));
}
}
经典问题
- 算法思想之动态规划(二)——最小路径和问题
- 算法思想之动态规划(三)——找零钱问题
- 算法思想之动态规划(四)——最长公共子序列问题
- 算法思想之动态规划(五)——最小编辑距离问题
- 算法思想之动态规划(七)——背包问题
未来几篇博文，我将继续对经典的动态规划问题进行整理，敬请关注~
由于本人水平有限，文章难免有欠妥之处，欢迎大家多多批评指正！
写在最后
欢迎大家关注我的个人博客复旦猿。
