当前位置: 首页 > news >正文

阿里网站建设百度注册公司地址

阿里网站建设,百度注册公司地址,免费wordpress主机,国外对网站开发的研究300. 最长递增子序列 1.dp定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 2.递推公式:if (nums[i] > nums[j]) dp[i] max(dp[i], dp[j] 1); 注意这里不是要dp[i] 与 dp[j] 1进行比较,而是我们要取dp[j] 1的最大值…

300. 最长递增子序列

1.dp定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2.递推公式:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值

 3.初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}
};

674. 最长连续递增序列

1.dp定义:dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]

2.递推公式:如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。

即:dp[i] = dp[i - 1] + 1;

因为本题要求连续递增子序列,所以就只要比较nums[i]与nums[i - 1],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)。

 3.dp[i]应该初始1;        

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};

718. 最长重复子数组

1.dp定义:以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。

2.递推公式:当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;

根据递推公式可以看出,遍历i 和 j 要从1开始!

3.初始化:根据dp[i][j]的定义,dp[i][0] 和dp[0][j]其实都是没有意义的!

但dp[i][0] 和dp[0][j]要初始值,因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;

所以dp[i][0] 和dp[0][j]初始化为0。

举个例子A[0]如果和B[0]相同的话,dp[1][1] = dp[0][0] + 1,只有dp[0][0]初始为0,正好符合递推公式逐步累加起来。

注:如果dp数组以i,j为结尾,那么初始化时,应该为dp[i] = dp[j]时初始化为1

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

http://www.yayakq.cn/news/424821/

相关文章:

  • 爱站关键词挖掘工具汕头住房与城乡建设网站
  • 网站开发高级证网页制作与网站建设宝典(第2版)
  • 爬虫网站开发营销型网站有哪些建设流程
  • 网站策划布局新闻类网站设计
  • 怎么制作网站摄影师常用的网站
  • 河北营销型网站建设石家网站建设公司排名
  • 企业门户网站建设费用旅游网页设计页面 模板html
  • 静态网站 后台电脑科技网站模板
  • 深圳网站建设 东莞网站建设做推广网站有什么
  • 淘宝属于什么网站怎么做广州网络seo公司
  • 企业门户网站建设情况汇报万网域名备案网站
  • dw网站建设教程视频wordpress代码seo
  • 阿里云网站怎么备案域名解析自动优化网站建设
  • 快速搭建网站服务器安卓软件开发软件
  • 建设网站的项目策划书网页案例集锦
  • 建站服务搭建的页面时外贸商城网站
  • 网站怎么制作商城怎样制作网站积分系统
  • wordpress图片站网站开发需要代码吗
  • 网站程序模块如何在虚拟空间上做多个网站
  • 网页设计设计一个网站wordpress的cookies
  • 青岛网站维护汽车网站建设预算
  • 专业做外贸网站的公司甜品网站开发需求分析
  • 国家建设部投诉网站做单页网站怎么选产品
  • 外贸网站推广平台有哪些专业的网站建设企业网站
  • 井陉矿区网站建设网站建设收费标准渠道
  • 四会网站建设seo排名优化推荐
  • 网站优化是什么长江证券官方网站下载
  • 手机网站建设制作微信小程序开发平台
  • 哪些网站权重高frontpg做网站好吗
  • 一个网站建设需要什么重庆建设银行官方网站首页