动态规划专练:力扣第300、674题-北京尧图网络

力扣第300题-最长递增子序列1.本题可以使用动态规划来解dp数组含义为到当前元素为止的最大递增子序列长度所有元素自身就是一个子序列都初始化为1。遍历一遍数组找到比当前元素小的值看当前元素是否要接续到该元素后面则递推公式为dp[i] fmax(dp[i], dp[j] 1)。完整代码如下1. int lengthOfLIS(int* nums, int numsSize) { 2. // dp[i]以nums[i]结尾的最长递增子序列长度 3. int dp[numsSize]; 4. dp[0] 1; 5. // 记录全局最长递增子序列长度 6. int res 1; 7. 8. // 遍历每个数字作为子序列末尾 9. for (int i 1; i numsSize; i){ 10. // 初始自身构成长度为1的子序列 11. dp[i] 1; 12. // 遍历i之前所有数字寻找更小的前缀 13. for (int j 0; j i; j){ 14. // 前面数字更小可拼接形成更长子序列 15. if (nums[j] nums[i]) dp[i] fmax(dp[i], dp[j] 1); 16. } 17. // 更新全局最大值 18. res fmax(res, dp[i]); 19. } 20. 21. return res; 22. }该算法时间复杂度为O(n2)空间复杂度为O(n)。2.本题的进阶方法需要使用贪心二分方法贪心的策略就是“要想长得长每次就得长得慢”。维护一个数组d存储“长度为i的递增子序列的最小末位元素”。遍历数组如果当前元素比d的最后一个元素大说明可以直接接续上去递增子序列的长度也1否则就去数组d中进行二分查找找出第一个比该元素大的元素进行替换。形象地说d数组记录着各个长度下的“最佳潜力股”。3.基于以上思想可写出完整代码如下1. int lengthOfLIS(int* nums, int numsSize) { 2. if (numsSize 0) { 3. return 0; 4. } 5. 6. // d 数组长度最多为 numsSize 1 7. // d[i] 表示长度为 i 的最长上升子序列的末尾元素的最小值 8. // 注意d 数组的索引是从 1 开始的d[1] 到 d[len] 9. int* d (int*)malloc(sizeof(int) * (numsSize 1)); 10. 11. d[1] nums[0]; // 初始化长度为 1 的最佳结尾是第一个元素 12. int len 1; // 当前最长递增子序列的长度 13. 14. for (int i 1; i numsSize; i) { 15. // 如果当前数字比目前最长序列的结尾还要大直接追加长度 1 16. if (nums[i] d[len]) { 17. len; 18. d[len] nums[i]; 19. } 20. else { 21. // 否则使用二分查找在 d[1] 到 d[len] 中找 22. // 找什么找最后一个小于 nums[i] 的数字的位置 23. int l 1, r len, pos 0; 24. 25. while (l r) { 26. int mid l (r - l) / 2; // 防止溢出的标准写法 27. 28. if (d[mid] nums[i]) { 29. // 找到了一个比 nums[i] 小的数先记录下它的位置然后继续往右边逼近 30. pos mid; 31. l mid 1; 32. } else { 33. // 如果 d[mid] nums[i]说明我们要找的在左半边 34. r mid - 1; 35. } 36. } 37. 38. // 循环结束后pos 是最后一个【严格小于】nums[i] 的元素的位置 39. // 那么 pos 1 就是第一个【大于等于】nums[i] 的元素的位置 40. // 用 nums[i] 替换掉它使得该长度的序列末尾变得更小潜力更大 41. // (特例如果所有数都 nums[i]pos 还是初始值 0此时刚好更新 d[1] nums[i]) 42. d[pos 1] nums[i]; 43. } 44. } 45. 46. // 释放动态分配的内存 47. free(d); 48. 49. // d 数组的最终长度就是整个数组的最长递增子序列的长度 50. return len; 51. }该算法时间复杂度为O(nlogn)空间复杂度为O(n)。力扣第674题-最长连续递增序列1.本题先尝试使用动态规划来做dp数组的含义为“当前长度下的最长连续递增序列的长度”dp[0]初始化为1。遍历一遍数组当前元素比上一个元素大时将计数器cnt 1取dp[i – 1]和cnt 1中的较大值否则就将cnt置为1并让dp[i]的值保持和dp[i – 1]一致。完整代码如下1. int findLengthOfLCIS(int* nums, int numsSize) { 2. // dp[i]前i个元素中最长连续递增子数组长度 3. int dp[numsSize]; 4. dp[0] 1; 5. // cnt以当前i结尾的连续递增子数组长度 6. int cnt 1; 7. 8. for (int i 1; i numsSize; i){ 9. if (nums[i] nums[i - 1]){ 10. // 当前数字比前一个大连续长度1 11. cnt; 12. dp[i] fmax(dp[i - 1], cnt); 13. } else { 14. // 不满足递增连续长度重置为1 15. cnt 1; 16. dp[i] dp[i - 1]; 17. } 18. } 19. 20. return dp[numsSize - 1]; 21. }该算法时间复杂度和空间复杂度均为O(n)。2.本题还是使用贪心算法更简便只要目前满足递增就将计数器cnt 1否则就将res和cnt的较大值存入rescnt置为1。最后不要忘记额外进行一次res fmax(res, cnt)来防止数组本身就是一个连续递增序列的情况。完整代码如下1. int findLengthOfLCIS(int* nums, int numsSize) { 2. // res全局最长连续递增子数组长度 3. int res 1; 4. // cnt以当前位置结尾的连续递增子数组长度 5. int cnt 1; 6. for (int i 1; i numsSize; i){ 7. if (nums[i] nums[i - 1]){ 8. // 保持连续递增当前连续长度1 9. cnt; 10. } else { 11. // 递增中断更新全局最大值并重置当前连续长度 12. res fmax(res, cnt); 13. cnt 1; 14. } 15. } 16. // 处理数组末尾一段连续递增未更新res的情况 17. res fmax(res, cnt); 18. 19. return res; 20. }该算法时间复杂度为O(n)空间复杂度为O(1)。

动态规划专练:力扣第300、674题

相关推荐

实测记录：免费开源视频压缩工具 CompressO 实测，229MB 视频几分钟压到 14MB

StarGAN-VC音色转换实战：非并行数据下的多对多语音风格迁移

CoPaw：开源个人AI助手如何重塑本地智能与数据隐私

更多资讯

3ds Max+Vray环境艺术效果图制作：从基础设置到渲染出图全流程规范

3ds Max+V-Ray环境艺术教程：软件概述与系统设置全攻略

AlexNet-BC：乳腺癌病理图像分类的经典骨架改造与实战要点

Flutter鸿蒙表单开发实战：从环境搭建到真机调试

AI视频生成技术全解：生成方法、操作流程与选型指南

AI 优化内容生成是什么？从RAG引用机制到GEO落地的实战指南

今日更新

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？