几题LCS后的小总结
2024-10-21 19:28:09
先得理解最长上升子序列吧,这还是非常简单的。
然后就是要真正理解LCS;
真正理解源于做题,做题就像查漏补缺一样,你总有不会的地方。
非常彻底地理解该图(还是去做题啦)
= =瞎几把乱说有两种问题
【完全的求一个最长公共子序列】
(非常彻底地理解路径或者说是状态转移的规律)
先是初始化
付一个0的dp数组,把dp作为一个介体达到一种最长公共子序列的目的
然后就开始更新dp的值,dp的状态转移方程OK,然后根据状态转移方程,
可以很清楚地知道,路径的变化就是状态转移变化的方向。
【这样就可以实现路径的初始模型】
【详细阐述路径】
就是标记啊,因为LCS问题上面,状态转移只有三种,向下,向右,还有右下,然后就是搞三个标记,在竖直方向上移动的话就是-1,在水平方向上移动的话就是1,然后如果满足了相等,要斜对角移动的话就是0,然后递归进行输出。
【反着的一个题目(拓展)】
另一个问题就是给你两个序列,再给你一个序列,然后问你前面两个序列能否组成被给的第三个序列。
DP求解:定义dp[i][j]表示A中前i个字符与B中前j个字符是否能组成C中的前 (i+j) 个字符,如果能标记true,如果不能标记false;
满足什么状态可以转变成什么状态;
可做的题(先去做求最大长度的练练手,然后理解路径,就可以做输出的题了):Hdoj3779,hdoj1501,poj2192,poj2250
【不会就去学,不要贴代码,思路最重要】
最新文章
- cnblog中添加数学公式支持
- Java学习——HashMap
- js禁止Backspace键使浏览器后退
- ldap + kerberos + google authentication 实现两步验证
- iOS 9/10强制使用https访问网络,使用了第三方SDK的应用需要配置的信息
- 学习WebSocket(一):Spring WebSocket的简单使用
- 总结一下安装linux系统经验-版本选择-安装ubuntu
- codeforces 711A A. Bus to Udayland(水题)
- PHP 文件上传的综合实例
- java事务的处理
- Strom学习笔记一
- 利用原生JavaScript获取样式的方式小结
- java IO流文件的读写具体实例
- 促销R语言应用性能
- 第二章_session管理
- js中的3种弹出式消息提醒(警告窗口,确认窗口,信息输入窗口)的命令式
- Linux/Windows 文件交互读取转义字符变换
- 探索PowerShell 【十三】WMI对象
- 一文看懂https如何保证数据传输的安全性的
- python之 可迭代 迭代器 生成器
热门文章
- 【剑指offer】打印1到最大的n位数
- break 用法
- 让Spring Boot启动更快
- 浅谈JavaScript的函数表达式(闭包)
- hive impala C++ Java垃圾回收 Garbage Collection GC
- ivy
- HDU 6118 度度熊的交易计划 【最小费用最大流】 (2017";百度之星";程序设计大赛 - 初赛(B))
- sql索引原理以及优化
- HDU3746 Cyclic Nacklace —— KMP 最小循环节
- ASP.NET Session and Forms Authentication and Session Fixation