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

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

前文提到了最长公共子序列问题，这是一个经典的动态规划问题。通过理解动态规划的本质，即利用子问题的最优解来构建原问题的最优解，我们可以迅速解决这类问题。实际上，只要掌握了动态规划的基本理念，即使是面对较为复杂的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

　　测试结果