动态规划最长上升子序列(Longestincreasingsubsequence)

前面写了最长公共子序列的问题。然后再加上自身对动态规划的理解真到简单的DP问题很快就解决了。其实只要理解了动态规划的本质那么再有针对性的去做这方的题

　　前面写了最长公共子序列的问题。然后再加上自身对动态规划的理解真到简单的DP问题很快就解决了。其实只要理解了动态规划的本质那么再有针对性的去做这方的题目思路很快就会有了。不错不错~加油

　　题目描述POJ2533

　　给出一个数列找出这个数列中最长上升子序列中所包含的个数。

　　解题思路

　　DP问题解题的一般方法就是自下而上即先求解小的问题然后再根据小的问题来解决大的问题最后得到解。但是这里还要满足的条件是最优子结构即最优解包含着其子问题的最优解。

　　那么我们首先用arr[]数组(从0下标开始)存储要求的数列用longest_num[i]数组来记录以i为结尾的子序列里面包含的最长上升子序列的数字个数。然后用循环控制从下标为1开始求longest_num并且记录找到的最大值即可得到解。在我的程序里面我还加了一个功能就是把最长上升子序列打印出来如果存在有多个的话那么就只打印最后一个。

　　最后根据下面的DP方程就可以进行求解了:

　　longest_num[i] max{longest_num[j] 1,longest_num[i]}     其中j

　　

#include #define MAX_N 1001int arr[MAX_N];int longest_num[MAX_N];int bt[MAX_N];int max_point 0;int LIS(int n){int max 1; //最长上升子序列的个数int i,j;for (i 0; i  　　测试数据

　　71 7 3 5 9 4 8

　　测试结果　　

　　

【转自：建湖网页制作公司 http://www.1234xp.com/jianhu.html 欢迎留下您的宝贵建议】