做网站公司哪个好,企业网站报价单,网站备案管局电话,阿里云 网站托管LIS #xff0c;#xff08;Longest Increasing Subsequence#xff09;本题链接#xff1a;895. 最长上升子序列 - AcWing题库 给定一个长度为 N的数列#xff0c;求数值严格单调递增的子序列的长度最长是多少。 目录
方法一#xff1a;暴力dfs 方法二#xff1a;记忆… LIS Longest Increasing Subsequence本题链接895. 最长上升子序列 - AcWing题库 给定一个长度为 N的数列求数值严格单调递增的子序列的长度最长是多少。 目录
方法一暴力dfs 方法二记忆化搜索
方法三dp 本篇将直接给出代码具体讲解请移步以下博客动态规划入门从暴力dfs到dp-CSDN博客
从01背包开始动态规划暴力解法 dp 滚动数组 dp优化-CSDN博客
方法一暴力dfs
找到最后一步以当前数作为子序列的结尾因此 f [ i ] 的含义为第 i 个数作为子序列结尾最长的上升子序列长度为多少递归选择当以第i个数作为结尾时遍历其前面所有的数而对于前面每一个数都有选和不选两种情况因为在dfs中尽可能减少参数因此当选择当前数时通过return 1的方式来表示当前数的子序列个数 1
#includeiostream
#includecmath
using namespace std;int n;
const int N 1010;
int nums[N];int dfs(int index){int res 0;for(int i 0;i index;i){if(nums[i] nums[index]) res max(res,dfs(i) 1);}return res;
}int main(){cin n;for(int i 0;i n;i) cin nums[i];int res -1e9;//将每一个数作为结尾for(int i 0;i n;i){res max(res,dfs(i));}cout res 1;return 0;
} 方法二记忆化搜索 增加一个mem数组用于存储
#includeiostream
#includecmath
using namespace std;int n;
const int N 1010;
int nums[N];
int mem[N];int dfs(int index){if(mem[index]) return mem[index];int res 0;for(int i 0;i index;i){if(nums[i] nums[index]) res max(res,dfs(i) 1);}mem[index] res;return res;
}int f[N];int main(){cin n;for(int i 0;i n;i) cin nums[i];int res -1e9;//将每一个数作为结尾for(int i 0;i n;i){res max(res,dfs(i));}cout res 1;return 0;
}
方法三dp
dp思路为枚举每一个数作为子序列结尾在枚举其倒数第二个数
#includeiostream
#includecmath
using namespace std;int n;
const int N 1010;
int nums[N];
int mem[N];int f[N];int main(){cin n;for(int i 0;i n;i) cin nums[i];int res -1e9;//将每一个数作为结尾for(int i 0;i n;i){f[i] 0;for(int j 0;j i;j){if(nums[j] nums[i])f[i] max(f[i],f[j] 1);}res max(res,f[i]);}cout res 1;return 0;
}
以上是本文全部内容如果对你有帮助点个赞再走吧~ ₍˄·͈༝·͈˄*₎◞ ̑̑
