动态规划—线性dp之最长公共子串
问题
继续 LCS 的问题考虑(本来是一篇文章,我感觉拆开好点)
问题又出现变化了,现在如果,我们要求求最长公共子串,也就是在 LCS
的基础上,要求连续
最长公共字串(LCStr)就是两个序列中连续且相同的最长子序列(区别于
LCS 的 “不要求连续”)
序列 A:"ABCBDAB"
序列 B:"BDCAB"
对比维度
最长公共子序列(LCS)
最长公共字串(LCStr)
核心要求
元素相对顺序一致,不要求连续
元素连续且相对顺序一致
示例结果
"BCAB"(长度 4)
"AB" 或 "BD"(长度 2)
问题本质
找 “有序不连续” 的最长交集
找 “有序且连续” 的最长交集
那么问题就被定义为,给定两个字符串 S(长度 n)和 T(长度
m),找到它们之间长度最长的公共连续子串,输出其长度(若不存在则输出
0)。
image-20251116195531260
问题分析
根据 LCS 的基础,我们考虑动态规划
首先考虑状态定义
设 S 长度为...
动态规划之线性dp之最长公共子序列
问题
image-20251116192953141
问题分析
子序列是指从一个序列中删除部分元素(可以不删)后,剩余元素保持原有相对顺序形成的新序列(不要求连续)。
最长公共子序列,英文缩写为LCS(Longest Common
Subsequence)。其定义是,一个序列 S
,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则
S 称为已知序列的最长公共子序列。
LCS
问题是:给定两个序列(如字符串、数组),找出它们之间长度最长的公共子序列。
例如:
序列 a = "ABCBDAB",序列 b = "BDCAB"
它们的 LCS 是 "BCAB" 或 "BDAB",长度为
4。
LCS 的标准解法可以通过动态规划在相对高效的时间内解决
考虑这样的一个状态:
用 二维数组
f[i][j],表示,序列a的前i个元素与序列b的前j个元素的最长公共子序列长度。
那么现在问题就变成了考察末尾元素 a[i],b[j] 是否在公共的子序列中
根据 a[i] 和 b[j]...
JavaScript_part6—JQuery.md
什么是jQurey
简介
jQuery 是一个 JavaScript 函数库。
jQuery 是一个轻量级的”写的少,做的多”的 JavaScript 库。
jQuery 库包含以下功能:
HTML 元素选取
HTML 元素操作
CSS 操作
HTML 事件函数
JavaScript 特效和动画
HTML DOM 遍历和修改
AJAX
Utilities
使用 jQuery 库
jQuery 库位于一个 JavaScript 文件中,其中包含了所有的 jQuery
函数。
可以通过下面的标记把 jQuery 添加到网页中:
123<head> <script type="text/javascript" src="jquery.js"></script></head>
共有两个版本的 jQuery
可供下载:一份是精简过的,另一份是未压缩的(供调试或阅读)。
这两个版本都可从 jQuery.com
下载。
Google 和...
JavaScript part5—BOM常见对象及其属性和JS操作BOM
BOM常见对象及其使用JS操作
BOM(Browser Object Model,浏览器对象模型)是 JavaScript
操作浏览器功能的接口,它以 window 为核心
window是整个BOM树食物链的顶端,因此每一个新打开的窗口,都被认为是一个window对象。
image-20251116152026607
window 是 BOM 的顶层对象,代表整个浏览器窗口,所有 BOM
对象都是 window 的属性。
全局变量和全局函数会自动成为 window 的属性(例如
window.alert() 可简写为 alert())。
window 可省略(如 window.location 可简写为
location)。
window.location:控制地址栏与页面跳转
location 对象管理当前页面的 URL 信息,可用于获取 URL
细节或跳转页面。
属性 / 方法
说明
href
获取或设置完整...
JavaScript part4—JS操作DOM及其DOM事件
什么是DOM和BOM
JavaScript的三大组成部分
image-20251116144529390
上面这张图,我们可以看到有四个元素:JavaScript,ECMAScript,DOM和BOM,那么它们四个之间有什么联系呢?
1JavaScript = ECMAscript + BOM + DOM
ECMAScript 是一种由 ECMA国际(前身为欧洲计算机制造商协会)通过
ECMA-262
标准化的脚本程序设计语言,它是JavaScript(简称JS)的标准,浏览器就是去执行这个标准。
ECMAscript更像一个规定,规定了各个浏览器怎么样去执行JavaScript的语法,因为我们知道JavaScript是运行在浏览器上的脚本语言!有了规定,但是我们还缺少与页面中各个元素交互的方式,此时下面的DOM诞生了!
DOM
Document Object Model,文档对象模型
简单说,DOM 是浏览器将 HTML
文档解析后生成的树状结构对象,它将 HTML
中的每个标签、文本、属性等都转换成可被 JS 操作的 “对象”,让...
动态规划之线性dp之最长上升子序列
问题
这是经典的 LIS 问题
image-20251115195703334
最长上升子序列是指,从原序列中按顺序取出一些数字排在一起,这些数字是逐渐增大的。
分析
那么考虑动态规划,我们设计一个 dp[i]
数组,表示以数组第i个元素(a[i])为结尾的最长上升子序列的长度。
为什么要 “以a[i]结尾”?因为 LIS
是严格递增的,后续元素要接在a[i]后面,必须满足比a[i]大,这样才能通过dp[i]推导后续状态。
从第一个数字开始推,所以说,dp[i] = 1
是关键初始化,因为每个元素本身可以单独构成一个长度为 1
的上升子序列,所以所有dp[i]的初始值都是 1。
那么我们需要遍历 i 之前的所有元素 j (从 0
到
i-1),对于每个i,遍历它前面所有的元素j:
如果a[i] > a[j](满足 “上升”
条件),说明a[i]可以接在以a[j]结尾的 LIS
后面,此时dp[i]可以更新为dp[j] + 1。
取所有满足条件的dp[j] + 1的最大值,就是dp[i]的最终值(即dp[i] =...
动态规划之01背包dp
问题
一个容量为 m 公斤的背包,现在有 n
种物品,每种物品只有一件,每件物品有其自身的重量
weight[i] 和价值 value[i]。
选择哪些物品装入背包,使得在不超过背包总承重的前提下,装入背包的物品总价值最大。
image-20251115191200115
思路
这就是著名的0-1背包问题。“0-1”意味着每种物品只有一件,你只能选择装入(1)或不装入(0),不能只装入部分。
要解决 01
背包问题,我们可以使用动态规划的方法。核心思路是通过一个二维数组
dp 来记录状态,其中 dp[i][j] 表示前
i 件物品在背包容量为 j
时能获得的最大价值。
那么每种物品只有一件,选择时只有 “放入背包” 或
“不放入背包”...
使用supabase和netlify部署你的小规模程序
微信小程序
微信小程序的微信小程序号申请,开发者平台怎么搞就不说了
项目介绍
我们会以一个以 nodejs 的为基础构建的,后端使用 express +
nodejs,非前后端分离的小型项目页面为例子,最后部署到 netlify 上,因为
github page 因为某些不可名状的原因被 ban 了
https://github.com/ergou10086/ErgouSampleBlogFrame
这是示例的仓库地址
预览:https://keen-licorice-1a4ade.netlify.app/
项目结构如下
123456789101112131415161718192021222324252627282930313233343536373839404142ErgouSampleBlogFrame/├── src/│ ├── config/│ │ └── supabase.js # Supabase 配置│ ├── controllers/│ │ ├── authController.js #...
JavaScript part3—日期和函数类型详解
日期对象
日期对象用于处理日期和时间。
在 JavaScript 中,日期时间处理主要通过 Date
对象实现,它用于表示和操作时间。
Date 对象属性
属性
描述
constructor
返回对创建此对象的 Date 函数的引用。
prototype
原型链,所以我们可以为日期对象对象添加属性和方法。
但是由于原生 Date
方法在格式化、时区处理等场景不够便捷,所以我一般使用Day.js
创建 Date 对象
Date 是一个构造函数,需通过 new
关键字创建实例,常见创建方式有 4 种:
无参数
创建当前时间的 Date 对象(基于系统本地时间):
12const now = new Date();console.log(now); // 例如:2025-11-14T08:30:00.123Z(UTC 时间)
时间戳参数
milliseconds 参数是一个 Unix 时间戳(Unix Time
Stamp),它是一个整数值,表示自 1970 年 1 月 1 日...
JavaScript part2—JavaScript的基本语法
JavaScript 基础语法
浏览器与控制台使用JS
JavaScript代码可以直接嵌在网页的任何地方,由<script>...</script>包含的代码就是JavaScript代码,它将直接被浏览器执行。
在开发 JavaScript
应用时,浏览器是我们的主要战场,而浏览器的开发者工具(特别是控制台)则是我们调试和学习的基本交互位置。
一般我们把JavaScript代码放到一个单独的.js文件,然后在HTML中通过<script src="..."></script>引入这个文件:
12345678<html><head> <script src="/static/js/abc.js"></script></head><body> ...














