如何用动态规划求解最长递增子序列问题？

本文共计700个文字，预计阅读时间需要3分钟。

面对最长公共子序列问题，首先理解了动态规划的本质。通过将问题分解为更小的子问题，并存储这些子问题的解，我们可以快速解决整个问题。实际上，只需掌握动态规划的基本原理，就能针对具有针对性的DP问题迅速找到解决方案。例如，前面提到的最长公共子序列问题，通过理解动态规划的本质，就能轻松解决。

前面写了最长公共子序列的问题。然后再加上自身对动态规划的理解真到简单的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

　　测试结果