前言
今天我們繼續(xù)討論經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題之最長(zhǎng)上升子序列問(wèn)題遗锣。
最長(zhǎng)上升子序列問(wèn)題
問(wèn)題描述
給定一個(gè)數(shù)字序列A捶枢，求該序列中最長(zhǎng)上升子序列的長(zhǎng)度赴魁。例如A={1,4,2,5,3}规惰，其最長(zhǎng)上升子序列為{1,2,3}吝镣，因此最長(zhǎng)上升子序列的長(zhǎng)度為3堤器。
問(wèn)題分析
假設(shè)序列長(zhǎng)度為
，構(gòu)建一個(gè)長(zhǎng)度為
的一維數(shù)組
末贾，
代表了以
結(jié)尾的上升子序列的長(zhǎng)度闸溃。很顯然，
拱撵，最長(zhǎng)上升子序列的長(zhǎng)度為
辉川。
代碼實(shí)現(xiàn)
通過(guò)問(wèn)題分析拴测，可以很容易得用代碼實(shí)現(xiàn)昼扛，下面給出算法的java實(shí)現(xiàn)。
public class LongestIncreasingSubsequence {
public int getLIS(int[] A, int n) {
return core(A, n);
}
// 動(dòng)態(tài)規(guī)劃
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));
}
}
經(jīng)典問(wèn)題
- 算法思想之動(dòng)態(tài)規(guī)劃(二)——最小路徑和問(wèn)題
- 算法思想之動(dòng)態(tài)規(guī)劃(三)——找零錢(qián)問(wèn)題
- 算法思想之動(dòng)態(tài)規(guī)劃(四)——最長(zhǎng)公共子序列問(wèn)題
- 算法思想之動(dòng)態(tài)規(guī)劃(五)——最小編輯距離問(wèn)題
- 算法思想之動(dòng)態(tài)規(guī)劃(七)——背包問(wèn)題
未來(lái)幾篇博文，我將繼續(xù)對(duì)經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題進(jìn)行整理毅厚，敬請(qǐng)關(guān)注~
由于本人水平有限吸耿，文章難免有欠妥之處，歡迎大家多多批評(píng)指正伴网！
寫(xiě)在最后
歡迎大家關(guān)注我的個(gè)人博客復(fù)旦猿澡腾。
