自顶向下方法通过递归来实现最长递增子序列问题
时间: 2024-05-11 17:14:36 浏览: 16
自顶向下方法是一种动态规划的实现方式,通过递归解决问题。最长递增子序列问题是一个经典的动态规划问题,其解决方法可以使用自顶向下方法。
具体实现过程如下:
1. 定义递归函数:定义一个递归函数,该函数接受两个参数,即当前位置i和上一个位置j,返回以i为结尾,且以j为前一个元素的最长递增子序列的长度。
2. 定义记忆数组:为了避免重复计算,可以定义一个记忆数组dp[i][j],存储以i为结尾,且以j为前一个元素的最长递增子序列的长度。
3. 初始条件:dp数组的初始值都为-1。
4. 递归求解:在递归求解过程中,如果dp[i][j]已经被计算过,则直接返回dp[i][j];否则,遍历所有i之前的元素k,如果nums[k] < nums[i],则递归调用函数,计算dp[i][j]的值,并取所有递归调用的结果中的最大值,加1得到dp[i][j]的值。
5. 返回结果:最后,返回dp数组中的最大值即可。
代码实现如下:
```
int dp[1000][1000]; //记忆数组,初始化为-1
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int res = 0;
for(int i = 0; i < n; i++){
res = max(res, dfs(nums, i, i-1));
}
return res;
}
int dfs(vector<int>& nums, int i, int j){
if(i < 0) return 0;
if(dp[i][j] != -1) return dp[i][j];
int res = 1;
for(int k = 0; k < i; k++){
if(nums[k] < nums[i]){
res = max(res, dfs(nums, k, i-1) + 1);
}
}
dp[i][j] = res;
return res;
}
```