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

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

前文提到了最长公共子序列问题，这是一个经典的动态规划问题。通过理解动态规划的本质，即利用子问题的最优解来构建原问题的最优解，我们可以迅速解决这类问题。实际上，只要掌握了动态规划的基本理念，即使是面对较为复杂的DP问题，也能迅速找到解决方法。具体来说，就是理解动态规划的核心在于构建一个状态转移方程，然后根据这个方程填充一个二维数组，从而得到最终的结果。例如，面对最长公共子序列这一问题时，只需理解动态规划的基本原理，就能高效地解决它。

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

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

　　题目描述POJ2533

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

　　解题思路

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

　　那么我们首先用arr[]数组(从0下标开始)存储要求的数列用longest_num[i]数组来记录以i为结尾的子序列里面包含的最长上升子序列的数字个数。