动态规划4：最长递增子序列问题
引言在动态规划系列的前三篇文章中，我们分别学习了爬楼梯问题、最长公共子序列和01背包问题。今天我们将探讨另一个动态规划的经典问题——最长递增子序列（Longest Increasing Subsequence，LIS）。 最长递增子序列问题不仅是动态规划的核心问题之一，更是算法优化思想的绝佳体现。从朴素的O(n²)动态规划解法，到巧妙的O(nlogn)优化算法，这个问题展现了算法设计的精妙之处。 问题定义什么是递增子序列？递增子序列：从原数组中按照原有顺序选取若干元素，使得这些元素严格递增。 注意几个关键点： 保持原有顺序：不能改变元素在原数组中的相对位置 严格递增：后面的元素必须大于前面的元素 不要求连续：子序列的元素在原数组中可以不相邻 最长递增子序列问题给定一个整数数组，找到其中最长递增子序列的长度。 经典例题：LeetCode 300. 最长递增子序列 1234567891011121314示例 1：输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,18]，因此长度为 4。示例 2：输入：nums = [0...
动态规划3：01背包问题
引言在前面的文章中，我们学习了动态规划入门和最长公共子序列问题。今天我们将探讨动态规划中最为经典和重要的问题之一——01背包问题。 01背包问题是动态规划的核心问题，它不仅在算法面试中频繁出现，更是理解动态规划思想的绝佳案例。掌握了01背包，你就掌握了一把解决众多动态规划问题的钥匙。 问题描述01背包的基本定义有一个容量为 W 的背包和 n 个物品，每个物品有两个属性： 重量 weight[i]：第 i 个物品的重量 价值 value[i]：第 i 个物品的价值 目标：在不超过背包容量的前提下，选择若干物品装入背包，使得背包中物品的总价值最大。 约束条件： 每个物品只能选择一次（0 或 1），这就是 “01” 的含义 所选物品的总重量不能超过背包容量 经典例题例题：LeetCode 416. 分割等和子集 给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 123456789示例 1：输入：nums = [1,5,11,5]输出：true解释：数组可以分割成 [1, 5, 5] 和 [11]。示例 2：输入：...
动态规划2：最长公共子序列问题
引言在上一篇文章中，我们通过爬楼梯问题初步了解了动态规划的基本思想。今天，我们将深入学习一个更加经典且实用的动态规划问题——最长公共子序列（Longest Common Subsequence，LCS）。 这个问题不仅在算法面试中频繁出现，在实际开发中也有广泛应用，比如： 版本控制系统中的文件差异比较 生物信息学中的DNA序列比对 文本编辑器的智能提示功能 问题定义什么是子序列？首先，我们需要明确子序列的概念： 子序列：从原序列中按照相对顺序选取若干元素组成的新序列 注意：子序列不要求连续，但必须保持相对顺序 例如，对于字符串 "ABCDEF"： "ACE" 是一个子序列 ✅ "BDF" 是一个子序列 ✅ "CAB" 不是子序列 ❌（顺序错误） 最长公共子序列问题给定两个序列，找到它们的最长公共子序列的长度。 例题：LeetCode 1143. 最长公共子序列 123输入：text1 = "abcde", text2 = "ace" 输出：3解释...
动态规划1：从爬楼梯问题开始
前言动态规划（Dynamic Programming，简称DP）是算法设计中的一种重要思想，它通过将复杂问题分解为子问题，并存储子问题的解来避免重复计算，从而提高算法效率。 作为动态规划系列的第一篇文章，我们将从最经典的入门题目——LeetCode第70题”爬楼梯”开始，深入理解动态规划的核心思想。 什么是动态规划？动态规划的核心思想是：将一个问题分解为若干个子问题，通过求解子问题并保存其结果，避免重复计算，最终得到原问题的解。 动态规划通常具备以下特征： 最优子结构：问题的最优解可以通过子问题的最优解来构造 重叠子问题：在求解过程中，同一个子问题会被多次计算 无后效性：一旦确定某阶段的状态，则此后过程的演变不再受此前各种状态及决策的影响 LeetCode 70. 爬楼梯题目描述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 示例 1： 12345输入：n = 2输出：2解释：有两种方法可以爬到楼顶。1. 1 阶 + 1 阶2. 2 阶 示例 2： 123456输入：n = 3输出：3解释：有三种方...
迁移记录：从VitePress到Hexo+Butterfly
前言作为一名技术博主，选择合适的博客框架是一个重要的决定。经过一段时间的使用和思考，我最终决定将博客从VitePress迁移到Hexo+Butterfly主题。这篇文章记录了完整的迁移过程，以及我在使用这两个工具过程中的心得体会。 迁移背景为什么要迁移？在使用VitePress的过程中，我遇到了一些问题： 格式问题频发：在处理复杂的Markdown格式时，VitePress经常出现渲染异常 主题定制困难：虽然VitePress很强大，但对于非前端专业的博主来说，深度定制比较困难 美观度不足：默认主题相对简洁，但缺少博客应有的丰富元素 插件生态有限：相比其他成熟的静态站点生成器，插件选择较少 基于这些考虑，我开始寻找更适合个人博客的解决方案。 VitePress vs Hexo：深度对比VitePress 特点分析优势方面： 现代化架构：基于Vite，构建速度极快 Vue生态：与Vue.js深度集成，对Vue开发者友好 开发体验：热重载、快速启动，开发体验优秀 TypeScript支持：原生支持TypeScript SEO友好：SSG（静态站点生成）对SEO有利 劣势方...
RAG技术详解：检索增强生成的革命性应用
简介RAG（Retrieval-Augmented Generation，检索增强生成）是一种结合了信息检索和文本生成的先进AI技术。它通过在生成过程中动态检索相关信息，显著提升了大语言模型的准确性和可靠性，特别是在处理需要特定领域知识或实时信息的任务时表现出色。 RAG的核心思想传统生成模型的局限性传统的生成模型（如GPT系列）虽然强大，但存在以下问题： 知识截止：训练数据有时间限制，无法获取最新信息 幻觉问题：可能生成看似合理但实际错误的内容 领域局限：对特定领域的深度知识可能不足 可解释性差：难以追溯生成内容的来源 RAG的解决方案RAG通过以下方式解决这些问题： 动态检索：实时从外部知识库检索相关信息 证据支撑：生成的内容有明确的信息来源 知识更新：可以轻松更新知识库而无需重训练模型 领域专业化：针对特定领域构建专门的知识库 RAG架构详解整体架构RAG系统通常包含三个核心组件： 123用户查询 → 检索器(Retriever) → 生成器(Generator) → 最终回答 ↓ 知识库(Knowledge Base) 核...
Transformer算法
简介Transformer是由Google在2017年提出的一种新型神经网络架构，它在论文《Attention Is All You Need》中首次亮相。这个模型彻底改变了自然语言处理（NLP）领域，成为了现代大型语言模型（如GPT、BERT）的基础架构。 Transformer的核心思想1. 注意力机制（Attention Mechanism）Transformer的核心创新在于完全基于注意力机制，摒弃了传统的循环神经网络（RNN）和卷积神经网络（CNN）。注意力机制允许模型在处理序列中的每个位置时，都能直接关注到序列中的任何其他位置。 2. 自注意力（Self-Attention）自注意力是Transformer的关键组件，它允许序列中的每个元素都能与序列中的所有其他元素建立直接连接，从而捕获长距离依赖关系。 Transformer架构详解整体架构Transformer采用编码器-解码器（Encoder-Decoder）结构： 编码器（Encoder）：将输入序列转换为连续的表示 解码器（Decoder）：根据编码器的输出生成目标序列 核心组件1. 多头注意力（Mu...
React框架指南
React 是由 Facebook 开发的一个用于构建用户界面的 JavaScript 库。它以其组件化架构、虚拟 DOM 和声明式编程范式而闻名，是现代前端开发的重要工具之一。 1. React 框架简介1.1 什么是 React？React 是一个专注于构建用户界面的 JavaScript 库，特别适用于构建单页应用程序（SPA）。它的核心思想是将用户界面分解为可重用的组件，每个组件管理自己的状态。 1.2 React 的核心特性 组件化：将 UI 分解为独立、可复用的组件 虚拟 DOM：提高性能的关键技术 单向数据流：数据从父组件流向子组件 JSX 语法：JavaScript 和 HTML 的完美结合 声明式编程：描述 UI 应该是什么样子，而不是如何实现 1234// React 组件示例function Welcome(props) { return <h1>Hello, {props.name}!</h1>;} 2. React 组件使用方式2.1 函数组件函数组件是最简单的定义组件的方式，它接收 ...
Element-UI指南
Element-UI 使用指南Element UI 是饿了么前端团队开源的一套基于 Vue.js 2.0 的桌面端组件库，提供了丰富的组件和优雅的设计风格，极大地提升了前端开发效率。 一、Element UI 简介1.1 特点 一致性：与现实生活一致，界面元素的外观应与现实世界的元素一致 反馈：通过界面样式和交互动效让用户可以清晰的感知自己的操作 效率：界面简单直白，让用户快速地理解并使用 可控：用户可以自由的进行操作，包括撤销、回退和终止当前操作等 1.2 安装方式123456# NPM 安装npm install element-ui --save# CDN 引入<script src="https://unpkg.com/element-ui/lib/index.js"></script><link rel="stylesheet" href="https://unpkg.com/element-ui/lib/theme-chalk/index.css"> 二、常用组件详解2...
Spring Boot 集成 Redis
🚀 Spring Boot集成Redis详解与面试要点Redis是一个高性能的key-value数据库，在Spring Boot项目中广泛用于缓存、会话管理等场景。本文将详细介绍如何在Spring Boot中集成Redis，以及Redis的核心特性和面试要点。 📋 目录 Redis基础概念 Spring Boot集成Redis Redis基本操作 缓存注解使用 Redis高级特性 性能优化与最佳实践 面试八股文 🔍 Redis基础概念Redis是什么？Redis (Remote Dictionary Server) 是一个开源的、基于内存的数据结构存储系统，可以用作数据库、缓存和消息代理。 核心特性1. 数据类型丰富12345678• String - 字符串• Hash - 哈希表• List - 列表• Set - 集合• ZSet - 有序集合• Stream - 流• Bitmap - 位图• HyperLogLog - 基数统计 2. 持久化方案 RDB: 快照持久化 AOF: 追加文件持久化 混合持久化: RDB + AOF...
