动态规划应用–最长递增子序列 LeetCode 300[通俗易懂]

动态规划应用–最长递增子序列 LeetCode 300[通俗易懂]文章目录1.问题描述2.解题思路2.1回溯法求解2.2动态规划1.问题描述有一个数字序列包含n个不同的数字,如何求出这个序列中的最长递增子序列长度?比如2,9,3,6,5,1,7这样一组数字序列,它的最长递增子序列就是2,3,5,7,所以最长递增子序列的长度是4。2.解题思路2.1回溯法求解/***@description:最长递增子序列*@author:m…

大家好,又见面了,我是你们的朋友全栈君。

1. 问题描述

有一个数字序列包含n个不同的数字,如何求出这个序列中的最长递增子序列长度?比如2,9,3,6,5,1,7这样一组数字序列,它的最长递增子序列就是2,3,5,7,所以最长递增子序列的长度是4。
https://leetcode-cn.com/problems/longest-increasing-subsequence/

2. 解题思路

2.1 动态规划

  • 假设在包含 i-1 下标数字时的最大递增子序列长度为 maxLen(i-1),那么下标为 i 时的 maxLen(i)需要考虑前面所有的状态,
  • 如果 a[j] < a[i] (0 <= j < i),则 maxlen[i] = max(maxlen[j]+1 | (0 <= j < i));
  • 如果 a[j] >= a[i] (0 <= j < i),则 maxlen[i] = 1;

借一张动图说明
在这里插入图片描述
在这里插入图片描述

class Solution 
{ 
   
public:
    int lengthOfLIS(vector<int>& nums) 
    { 
   
        int n = nums.size();
        if(n == 0)
            return 0;
        int maxlen[n], ans;
        int i, j;
        for(i = 0; i < n; ++i)
            maxlen[i] = 1;//至少为1,自己
        for(i = 1; i < n; ++i)
        { 
   
        	ans = 1;
            for(j = 0; j < i; ++j)
            { 
   
            	if(nums[i] > nums[j] && maxlen[j]+1 > ans)
            	{ 
   
            		ans = maxlen[j]+1;
            		maxlen[i] = ans;
            	} 
        	}
        }
        for(ans = 1, i = 0; i < n; ++i)
        { 
   
        	if(maxlen[i] > ans)//取最大值
        		ans = maxlen[i];
        }
        return ans;
    }
};
class Solution { 
   	//2020.3.14
public:
    int lengthOfLIS(vector<int>& nums) { 
   
        if(nums.size() == 0)
            return 0;
        int i, j, n = nums.size(),maxlen = 1;
        vector<int> dp(n,1);
        for(i = 1; i < n; ++i)
        { 
   
            for(j = i-1; j >= 0; --j)
            { 
   
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            }
            maxlen = max(maxlen, dp[i]);
        }
        return maxlen;
    }  
};

2.2 二分查找

  • 参考官方的解答
  • dp[i] 表示长度为 i+1 的子序的最后一个元素的 最小数值
  • 遍历每个 nums[i],找到其在dp数组中的位置(大于等于 nums[i] 的第一个数),将他替换成较小的

以输入序列 [0, 8, 4, 12, 2] 为例:

第一步插入 0,dp = [0]

第二步插入 8,dp = [0, 8]

第三步插入 4,dp = [0, 4]

第四步插入 12,dp = [0, 4, 12]

第五步插入 22,dp = [0, 2, 12]

class Solution { 

public:
int lengthOfLIS(vector<int>& nums) { 

if(nums.size() == 0)
return 0;
int i, l, r, n = nums.size(), maxlen = 1, idx;
vector<int> dp(n);
dp[0] = nums[0];
for(i = 1; i < n; ++i)//遍历每个数
{ 

l = 0, r = maxlen-1;
idx = bs(dp,l,maxlen,nums[i],maxlen);
//二分查找nums[i] 在dp中的位置
if(idx == maxlen)//nums[i] 是最大的
{ 

dp[idx] = nums[i];
maxlen++;
}
else//不是最大的,更新 dp[i] 里的数为较小的
dp[idx] = min(dp[idx], nums[i]);
}
return maxlen;
}  
int bs(vector<int> &dp, int l, int r, int& target, int& maxlen)
{ 
	//二分查找nums[i] 在dp中的位置, 第一个大于等于 nums[i] 的
int mid;
while(l <= r)
{ 

mid = l + ((r-l)>>1);
if(dp[mid] < target)
l = mid+1;
else
{ 

if(mid == 0 || dp[mid-1] < target)
return mid;
else
r = mid-1;
}
}
return maxlen;//没有找到,nums[i] 最大,放最后
}
};
  • 基于上面的想法,直接用 treeset 可以简化代码
class Solution { 

public:
int lengthOfLIS(vector<int>& nums) { 

if(nums.size() == 0)
return 0;
set<int> s;
for(auto& n : nums)
{ 

if(s.count(n))
continue;
else
{ 

auto it = s.upper_bound(n);//n的上界
if(it == s.end())//没有比我大的
s.insert(n);
else//有比我大的
{ 

s.erase(it);//删除比我大的
s.insert(n);//换成我
}
}
}
return s.size();
}
};

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/137616.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • python文件处理

    概念及作用(为什么用文件操作)计算机系统分为:计算机硬件,操作系统,应用程序三部分。我们用python或其他语言编写的应用程序若想要把数据永久保存下来,必须要保存于硬盘中,这就涉及到应用程序要操作

  • Pycharm 恢复到默认设置

    Pycharm 恢复到默认设置有时候我们想将软件的主题配色、插件等配置初始化,可是会发现卸载并重新安装Pycharm后,软件会默认使用卸载前的个性化设置。解决方案如下:点击Pycharm的“文件”菜单,里面有一个“管理IDE设置”的选项,然后点击“恢复默认设置”。……

  • 串口助手(简洁版)上位机软件零基础教程( C# + visual studio2017 )(一)[通俗易懂]

    串口助手(简洁版)上位机软件零基础教程( C# + visual studio2017 )(一)[通俗易懂]本人所在铁人战队的实验室同学们主要从事单片机的编程开发。但比赛和项目过程中,常常都需要与机器人进行人机交互。虽然实验室常用的HMI串口屏能满足我们的基本需求,但没东西在手的时候,就是个难题了。所以本文则介绍一下使用visualstudio软件,进行C#上位机软件的开发入门。以同学们常用的串口助手(简洁版)为例,来着手进行学习和入门。由于笔者知识有限,且是第一次写博客,有不足或错误之处,还…

  • 官网下载jdk要下载低版本的jdk总是找半天也找不到,怎么办[通俗易懂]

    官网下载jdk要下载低版本的jdk总是找半天也找不到,怎么办[通俗易懂]官网下载jdk要下载低版本的jdk总是找半天也找不到,怎么办

  • 随机梯度下降法和批量梯度下降法_梯度下降法优化

    随机梯度下降法和批量梯度下降法_梯度下降法优化深度学习最常用的优化方法就是随机梯度下降法,但是随机梯度下降法在某些情况下会失效,这是为什么呢?带着这个问题我们接着往下看。一个经典的例子就是假设你现在在山上,为了以最快的速度下山,且视线良好,你可以看清自己的位置以及所处位置的坡度,那么沿着坡向下走,最终你会走到山底。∑i=1n∇θf(θ;xi,yi)+∇θϕ(θ)\sum_{i=1}^{n}\nabla_{\theta}f\left(\theta;x_{i},y_{i}\right)+\nabla_{\theta}\phi(\theta

  • python激活码(破解版激活)

    python激活码(破解版激活),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号