寻找常州微信网站建设,网站推广100种方法,wordpress cdts小说,服务之家网站推广学习交流加 个人qq#xff1a; 1126137994个人微信#xff1a; liu1126137994学习交流资源分享qq群#xff1a; 962535112 这是一个经典的LIS(即最长上升子序列)问题#xff0c;请设计一个尽量优的解法求出序列的最长上升子序列的长度。
给定一个序列arr及它的长度n(长度小… 学习交流加 个人qq 1126137994个人微信 liu1126137994学习交流资源分享qq群 962535112 这是一个经典的LIS(即最长上升子序列)问题请设计一个尽量优的解法求出序列的最长上升子序列的长度。
给定一个序列arr及它的长度n(长度小于等于500)请返回LIS的长度。
测试样例 [2,1,5,3,6,4,8,9,7],9 返回5
分析思路化简到子问题那么这道题应该是化简到求该序列长度的前1,2,3,4,5,6…n个数的最长上升子序列问题
那么同样是开辟一个数组dp[n] 这里开辟的是数组还是矩阵是根据实际情况而来。那么dp[i]就代表必须以arr[i]结尾的情况下arr[0…i]的最长上升子序列的长度。 由上图的分析可知 dp[0]1; dp[1] 取决于arr[1]是否大于arr[0] 本题是不大于所以dp[1]1; dp[2]取决于arr[2]是否大于arr[j]j0~1大于arr[j]的话那么就取dp[j]1的最大值 dp[3]取决于arr[3]是否大于arr[j]j0~2大于arr[j]的话那么就取dp[j]1的最大值 dp[4]取决于arr[4]是否大于arr[j]j0~3大于arr[j]的话那么就取dp[j]1的最大值
那么dp[i]的表达式就应该是 dp[i]max{dp[j]1(j0~(i-1)),且arr[i]arr[j]}
由以上分析可写程序如下
class LongestIncreasingSubsequence {
public:int getLIS(vectorint A, int n) {// write code hereint dp[n];/* 初始化dp */for(int i0;in;i){dp[i]1;}int Max1;for(int i1;in;i){for(int j0;ji;j){if(A[i]A[j]){//注意dp[j]1这个表达式只能放到判断语句里面这样才不会改变它的值只做判断//如果改变了dp[j]的值将会影响下一次循环的计算if((dp[j]1)dp[i]) dp[i]dp[j]1;}}/* 外部每循环一次则求得了dp[i]的值选出每次循环后得到的最大值就是最终需要返回的值 */if(dp[i]Max)Maxdp[i];;}return Max;}
};动态规划的思想化整体为0,1,2…先计算子问题再合并计算整体问题
