尝试解释LIS（最长递增子序列）的一种动态规划算法

最长上升子序列就是求给定序列的最长的递增序列，其中不要求序列的元素在原序列中保持连续。

为了方便理解，可以举个例子：

inta[] = {0,2,1,5,3,6,4,8,9,7}(数组下标从1开始)的一个最长的子序列1,3,4,7,9。

利用动态规划的思想，可以方便的求取这个解。

为了方便解释，我们定义dp(n)为长度为1至下标为n的最长子序列的长度(数组下标假设从1开始)，{a[1],a[2],..,a[n]}为dp(n)对应的序列。

为了和程序对应，我采取自底向上的方式进行解释。

1.显然对于序列dp(1) 对应的{2}来说，最长递增子序列的长度就是1；

2.对于序列dp(2) 对应的{2,1},我们首先比较a[2]和a[1]大小，

若a[2]>a[1]，显然此时的{a[1],a[2]}是一个最长子序列，故dp(2) = dp(1)+1=2,

若a[2]<=a[1], 此时一个最长子序列的长度仍然为1，即dp(2) = 1;

在我们的例子中a[2]= 1 <a[1]=2,故dp(2)=1；

3.那么对于包含三个数的序列dp(3)对应的{2,1,5}来说呢

此时a[3]要和a[1], a[2]进行比较，此时可能会出现这种情况

a[3]>a[1]，由于子序列可以是不连续的，故{a[1],a[3]}可以是一个子序列，dp[3]=dp[1]+1

a[3]>a[2]，说明以a[2]为末端的子序列（可以不连续哦）+a[3]能形成一个新的子序列，此时要给dp[3]赋值，

那么dp[3]是等于dp[1]+1还是dp[2]+1呢

既然我们要求最长子序列，那么就要让dp[3]=max{dp[2],dp[1]}+1

若a[3]<a[1],a[3]<a[2]

还是令dp[3] = 1;

例子中a[3]>a[1],a[3]>a[2], dp[3]=max{dp[2],dp[1]}+1= 2

…………………………………………………

这样问题就就转化为在dp[1],dp[2],…,dp[n-1]的情况下如何求取dp[n]

若a[n]>a[i],a[n]>a[j],a[n]>a[k]….,(i,j,k…属于1至n-1)

dp[n]=max{dp[i],dp[j],dp[k],,,,,,}+1

若不满足

dp[n]=1

// DoubleLIS.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define N 10
int dp[N];//表示从A[1]到A[i]中以A[i]结尾的最长子序列长度
int a[N] = {0,2,1,5,3,6,4,8,9,7};

int LIS(int n)  //从左往右最长序列的长度
{
	int ans = 1;
	for (int i = 2; i < N; i++)
	{
		int tmp = i;
		int max = 0;
		for (int j = 1; j < i; j++)
		{
			//从左向右搜索dp数组，若满足上升序列的条件
			//1.若a[i] > a[j]
			//找到dp数组中最大的值，即A[i]之前最大的值
			//2.若a[i]不满足a[i] > a[j]
			//则dp[i] = 1
			if (a[i] > a[j] && dp[j] > max)
			{
				tmp = j;
				max = dp[j];
			}
		}

		//最大值+1就是dp[i]
		dp[i] = dp[tmp] + 1;

		if (dp[i] > ans)
			ans = dp[i];
	}
	
	return ans;

}
int main(int argc, char* argv[])
{
	dp[1] = 1;
	printf("%d\n", LIS(N-1));  //从左往右最长序列的长度
	return 0;
}

尝试解释LIS（最长递增子序列）的一种动态规划算法,布布扣,bubuko.com

尝试解释LIS（最长递增子序列）的一种动态规划算法

原文：http://blog.csdn.net/lampqiu/article/details/38536637