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

lc1035-不相交的线

题目描述

  • “连连看”
  • 上下两个数组,相同的数可以连线,问在不交叉的情况下最多可以连多少条线

示例

输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:
1 4 2
|  \
1 2 4
输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3
输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2

题解

  • 思路
    • 暴力就是枚举两个末尾,然后穷举
    • 这种暴力要优化就是 DP
func maxUncrossedLines(nums1 []int, nums2 []int) int {n, m := len(nums1), len(nums2)f := make([][]int, n + 1)for i := 0; i < n + 1; i ++ { f[i] = make([]int, m + 1) }for i := 1; i <= n; i ++ {for j := 1; j <= m; j ++ {f[i][j] = max(f[i - 1][j], f[i][j - 1])if nums1[i - 1] == nums2[j - 1] {f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)}}}return f[n][m]
}
http://www.hskmm.com/?act=detail&tid=16223

相关文章:

  • 自我介绍与未来规划
  • 解构React Server Components:服务端序列化与流式传输的底层逻辑
  • js里面的单引号、双引号及反引号的用法
  • 牛客刷题-Day4
  • Skinned Mesh Renderer与LOD系统蒙皮变形异常全解析
  • K8S (Containerd)初始化安装流程
  • ?模拟赛 赛后总结
  • 日志|动态规划|最长回文子串|最长公共子序列|HTML CSS
  • Java 字段命名避坑: success和isSuccess
  • OTA升级时软件异常复位问题分析
  • Atcoder Educational DP Contest 做题记录
  • 20250924
  • 跨端边云时序数据管理新范式:Apache IoTDB 的 DB+AI 融合之道 - 实践
  • 《Real-Time Rendering》第二章 图形渲染管线
  • 放弃Unity后,我为什么选择了Unigine?
  • PHP 与 Java 的终极对比:2025年,开发者该如何选择? - 详解
  • 题单63——流程控制
  • 银行同业存单的信用等级
  • 软件技术基础第一次作业
  • 2025XDOJ个人题解——写在前面
  • 适合电子纸屏幕的简易象棋打谱程序
  • 0924
  • java_string比较中的细节
  • 扫描线学习笔记
  • go-reids
  • AI完美声音克隆及情绪控制,与真人无异,Lark下载介绍
  • WSL,适用于 Linux 的 Windows 子系统
  • 9-24
  • 代码随想录算法训练营第八天 |344.反转字符串、541. 反转字符串II、LCR 122. 路径加密
  • 9/24