[ACM_动态规划] 最长上升子序列（LIS）2021-12-21 03:09:15 问题描述：给n个数，找出最长子序列并输出 问题分析：本题是DAG（有向无环图）最长路问题，设d[i]为以i结尾的最长链的长度，则状态转移方程为：d[i]=max{0,d[j]|j<i && A[j]<A[i]}+1 ; solve one: 这里用map[i][j]存储第i个和第j个的关系0-1邻接矩阵;套用标准解DAG的模板，利用dfs求解 View Code solve two:正向求解，边输边计算d[]的值 View Code 标签: LIS, 最长上升子序列, 动态规划, 记忆化搜索, dfs, 反向追踪, DAG, ACM_动态规划 本文转自beautifulzzzz博客园博客，原文链接：http://www.cnblogs.com/zjutlitao/p/3219522.html，如需转载请自行联系原作者 上一篇：“懒惰”Linux管理员的10个关键技巧下一篇：OPUS编解码器简介