经典动态规划:子序列问题-01(LC300)

题目:输入是一个一维数组,输出是一个正整数,表示最长递增子序列的长度

注意: 按照 LeetCode 的习惯,子序列(subsequence)不必连续,子数组(subarray)或子字符串(substring)必须连续。

题解:对于子序列问题,第一种动态规划方法是,定义一个 dp 数组,其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后,统计一遍各个位置的结果即可得到题目要求的结果。在本题中,dp[i] 可以表示以 i 结尾的、最长子序列长度。对于每一个位置 i,如果其之前的某
个位置 j 所对应的数字小于位置 i 所对应的数字,则我们可以获得一个以 i 结尾的、长度为 dp[j]
+ 1 的子序列。为了遍历所有情况,我们需要 i 和 j 进行两层循环,其时间复杂度为 O(n2)。

class Solution {
    public int lengthOfLIS(int[] nums) {
    if(nums.length==0){
        return 0;
    }
    int[]dp=new int[nums.length];
    dp[0]=1;
    int maxans=1;
    for(int i=0;i<nums.length;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){//i大于j的,就用状态转移方程,选择大的数
            dp[i]=Math.max(dp[i],dp[j]+1);

            }
        }
        maxans=Math.max(maxans,dp[i]);
    }
    return maxans;
        }
}

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-09 22:57
安徽大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-27 14:49
韶关学院_2022
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议