作者：Harris
背包问题九讲 2.0 beta1.2
背包问题九讲 2.0 beta1.2 本文题为《背包问题九讲》，从属于《动态规划的思考艺术》系列。 2011 年 9 月，本系列文章由原作者用 LaTeX 重新制作并全面修订，您现在看到的是 2.0 beta1.2 版本，修订历史及最新版本请访问 https://github.com/tianyic
重构线性代数（一）：基石与视界 —— 向量与线性空间
重构线性代数 (一)：基石与视界 —— 向量与线性空间 在传统的大学课堂上，线性代数往往被教成了一门“算术课”——如何计算矩阵相乘、如何用高斯消元法解方程、如何套公式求逆矩阵。但如果只停留在数字的机械运算上，当你面对计算机图形学、机器学习或高级算法时，你会感到寸步难行。 本系列旨在为你建立线性代数的
环形 DP 的数学本质：状态转移图与矩阵的迹
环形 DP 的数学本质：状态转移图与矩阵的迹 —— 洛谷 P1357 花园 背后的线性代数原理 在解决《花园》这道题时，我们使用到了“状态压缩”和“矩阵快速幂”。但如果不从纯数学的角度去理解它，这就只是一套死记硬背的代码模板。 本文将剥开代码的外衣，从图论 (Graph Theory) 和 线性代数
组合数学与 DP 优化：硬币购物（容斥原理经典模型）
组合数学与 DP 优化：硬币购物 (容斥原理经典模型) —— 洛谷 P1450 [HAOI2008] 深度解析 题目简述：共有 4 种硬币，面值分别为 c_1, c_2, c_3, c_4。进行 T 次询问，每次询问给出这 4 种硬币的数量限制 d_1, d_2, d_3, d_4，问凑出总价值 s
矩阵快速幂与环形状压 DP：洛谷 P1357 花园详解
矩阵快速幂与环形状压 DP：洛谷 P1357 花园 详解 题目简述：有一个周长为 N 的环形花园，每个位置可以种 'C' 或 'P' 两种花。要求任意连续的 M 个位置中，'C' 的数量不能超过 K 个。求合法的种植方案数，对 10^9 + 7 取模。 数据范围：4 \leq N \leq 10^{
轮廓线 DP：网格图上的状态压缩艺术
轮廓线 DP (Broken Profile DP)：网格图上的状态压缩艺术 在处理棋盘、网格图的覆盖问题时（例如骨牌铺满问题、哈密顿路径计数），我们经常会想到状态压缩 DP。传统的状压 DP 通常是“逐行转移”的：用一个二进制数表示第 $i$ 行的状态，推导第 $i+1$ 行。但逐行转移的痛点在于
围棋状态空间复杂度的数学推导与计算
围棋：极简规则与状态空间的数学推导 围棋（Go / Weiqi）是世界上最古老且最复杂的棋类游戏。它的规则极其简单，但由于棋盘广阔、落子自由，其演化出的变化数量超越了可观测宇宙中的原子总数。本文将系统梳理围棋的核心规则，并从计算机科学的角度，详细推导围棋“合法棋面数量（状态空间）”的计算方法与震撼结
数论核心：乘法逆元详解与三大算法实现
数论核心：乘法逆元 (Modular Multiplicative Inverse) 详解与算法实现 在算法竞赛和密码学中，我们经常会遇到要求将最终结果对某个大质数（如 10^9+7 或 998244353）取模的情况。 对于加、减、乘法，模运算都满足分配律，我们可以一边计算一边取模。但是，除法是不
深入浅出杨表：从组合数学到算法降维打击
深入浅出杨表 (Young Tableau)：从组合数学到算法降维打击 在普通算法视角下，求解最长上升子序列 (LIS) 需要用到动态规划。但如果题目要求我们统计**“所有可能排列中，LIS 长度的期望/总和”**，动态规划就会面临状态爆炸的绝境。 此时，我们需要引入组合数学中的核武器——杨表 (Y
深入通俗理解“卷积”：从数学物理到深度学习
深入通俗理解“卷积”：从数学物理到深度学习 无论是在信号与系统课程中，还是在学习卷积神经网络（CNN）时，“卷积 (Convolution)”都是一个绕不开的幽灵。初学者往往会被它的数学积分公式吓倒，但如果你懂得了它的物理意义，就会发现这是一个极其优雅且自然的概念。 一、 到底什么是“卷积”？（一个